首页 > 代码库 > 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;}
UVA 567 Risk
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。