首页 > 代码库 > UVA 567 Risk

UVA 567 Risk

flyod 就可以 ,N只有20.不过感觉直接BFS好像行?

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 25const int INF = 0x3f3f3f3f;int dist[MAXN][MAXN];int cnt;void read(){    memset(dist,0x3f,sizeof(dist));    for (int i = 1; i <= cnt; i++)    {        int tmp;        scanf("%d",&tmp);        dist[1][tmp] = dist[tmp][1] = 1;    }    for (int i = 2; i <= 19; i++)    {        scanf("%d",&cnt);        for (int j = 1; j <= cnt; j++)        {            int tmp;            scanf("%d",&tmp);            dist[i][tmp] = dist[tmp][i] = 1;        }    }}int main(){    //freopen("sample.txt","r",stdin);    int kase = 1;    while (scanf("%d",&cnt) != EOF)    {        read();        for (int k = 1; k <= 20; k++)            for (int i = 1; i <= 20; i++)              for (int j = 1; j <= 20; j++)                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);        int N;        scanf("%d",&N);        printf("Test Set #%d\n",kase++);        for (int i = 1; i <= N; i++)        {            int u,v;            scanf("%d%d",&u,&v);            printf("%2d to %2d: %d\n",u,v,dist[u][v]);        }        putchar(\n);    }    return 0;}
View Code

 

UVA 567 Risk