最短路

题解

poj 1611
题意：
有m个区域，n个小镇，有c个人在这些小镇中，他们要去某一个区域中聚会，从一个区域到另一个区域需要穿墙，问这些人聚到一起最少需要穿过几道墙。
题中给出的区域是用小镇描述的，某几个小镇围成一个区域，每一个区域按照顺时针方向给出的。
思路：
首先用两个vector，一个描述一个区域，属性是这个区域的边界有哪些点，另一个描述一个点，属性是这些点属于哪个区域。然后接下来，我们把每一个区域看成一个点，开始建图。
这题的难点就在于怎么建图，首先我们把一个区域看成一个点，那么怎么才能知道两个区域相邻呢？由于描述每个区域的点是以顺时针方向给出的，所以对于每个区域，当我们把每个区域的店push_back完之后，再把这个区域的点push_back进去，那么就相当于这些点构成了一个环,对于相邻的两点，如果说vis[点j][点j+1]没有东西的话，那么这个的值就等于这个区域，如果有值的话，那么就说明保存的值与当前的区域是相邻的，就把距离赋值为1，泽阳就把建图的问题解决了。
之后就是求任意两个区域的最短距离，用到了floyd算法，这倒是一个新姿势，不过很简单，就是把两点之间的距离通过图上的每一个点松弛。

代码：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<int> r[400],t[400];
int club[40];
int g[400][400];
int vis[400][400];
int main()
{
    int m,n,c;
    memset(r,0,sizeof(r));
    memset(t,0,sizeof(t));
    scanf("%d%d%d",&m,&n,&c);
    memset(g,inf,sizeof(g));
    for (int i = 1;i <= 399;i++) g[i][i] = 0;
    for (int i = 0;i < c;i++) scanf("%d",&club[i]);
    for (int i = 1;i <= m;i++)
    {
        int o;
        scanf("%d",&o);
        for (int j = 0;j < o;j++)
        {
            int oo;
            scanf("%d",&oo);
            r[i].push_back(oo);
            t[oo].push_back(i);
        }
        r[i].push_back(r[i][0]);
    }
    for (int i = 1;i <= m;i++)
    {
        for (int j = 0;j < r[i].size() - 1;j++)
        {
            int fr = r[i][j],to = r[i][j+1];
            if (vis[fr][to]) g[vis[fr][to]][i] = g[i][vis[fr][to]] = 1;
            else vis[fr][to] = vis[to][fr] = i;
        }
    }
    for (int i = 1;i <= m;i++)
        for (int j = 1;j <= m;j++)
        for (int k = 1;k <= m;k++)
    {
        if (g[j][k] > g[j][i] + g[i][k])
            g[j][k] = g[j][i] + g[i][k];
    }
    int ans = inf;
    for (int i = 1;i <= m;i++)
    {
        int sum = 0;
        for (int j = 0;j < c;j++)
        {
            int minn = inf;
            int cc = club[j];
            for (int k = 0;k < t[cc].size();k++)
            {
                int w = t[cc][k];
                minn = min(minn,g[w][i]);
            }
            sum += minn;
        }
        ans = min(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}