最短路问题:floyd算法:
注意:输出格式
#include<stdio.h> #define MAXN 200 int a, b, n, d[30][30], num; void init() { num = 0; while(scanf("%d",&a) == 1) { for(int i = 1; i <= 20; i ++) for(int j = 1; j <= 20; j ++) if(i == j) d[i][j] = 0; else d[i][j] = MAXN; if(a != 0) for(int i = 0; i < a; i ++) { scanf("%d",&b); d[1][b] = 1; d[b][1] = 1; } for(int i = 2; i < 20; i ++) { scanf("%d",&a); if(a != 0) for(int j = 0; j < a; j ++) { scanf("%d",&b); d[i][b] = 1; d[b][i] = 1; } } for(int k = 1; k <= 20; k ++) for(int i = 1; i <= 20; i ++) { for(int j = 1; j <= 20; j ++) d[i][j] = (d[i][j] < (d[i][k] + d[k][j]) )? d[i][j] : (d[i][k] + d[k][j]); } num ++; printf("Test Set #%d\n",num); scanf("%d",&n); for(int i = 0; i < n; i ++) { scanf("%d%d",&a,&b); printf("%2d to %2d: %d\n",a,b,d[a][b]); } puts(""); } } int main() { init(); return 0; }