UVa 567 Risk

题目描述题目要求计算给定无向图中两点之间的最短路径长度边数。图有202020个节点输入描述了111到191919的每个节点与更高编号节点的连接关系。然后给出若干查询输出从起点到终点的最短路径边数包括终点。输入格式输入包含多个测试集。每个测试集前191919行描述图第iii行1≤i≤191 \le i \le 191≤i≤19包含一个整数XXX表示与节点iii相邻的更高编号节点数然后XXX个整数JJJiJ≤20i J \le 20iJ≤20。第202020行是一个整数NNN1≤N≤1001 \le N \le 1001≤N≤100表示查询数。接下来NNN行每行两个整数AAA、BBB1≤A,B≤201 \le A, B \le 201≤A,B≤20A≠BA \ne BAB表示起点和终点。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个测试集输出Test Set #TTTT从111开始。然后对于每个查询输出一行格式为起点右对齐宽度222、to、终点右对齐宽度222、:、最短路径边数。每个测试集输出后跟一个空行。样例输入1 3 2 3 4 3 4 5 6 1 6 1 7 2 12 13 1 8 2 9 10 1 11 1 11 2 12 17 1 14 2 14 15 2 15 16 1 16 1 19 2 18 19 1 20 1 20 5 1 20 2 9 19 5 18 19 16 20 4 2 3 5 6 1 4 3 4 10 5 5 10 11 12 19 18 2 6 7 2 7 8 2 9 10 1 9 1 10 2 11 14 3 12 13 14 3 18 17 13 4 14 15 16 17 0 0 0 2 18 20 1 19 1 20 6 1 20 8 20 15 16 11 4 7 13 2 16输出Test Set #1 1 to 20: 7 2 to 9: 5 19 to 5: 6 18 to 19: 2 16 to 20: 2 Test Set #2 1 to 20: 4 8 to 20: 5 15 to 16: 2 11 to 4: 1 7 to 13: 3 2 to 16: 4题目分析本题的核心是计算所有点对之间的最短路径边权为111。可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法。算法初始化邻接矩阵country[i][j]\textit{country}[i][j]country[i][j]iji jij时为000有边时为111否则为∞\infty∞。运行Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法得到任意两点间最短路径长度。对于每个查询直接输出结果。复杂度分析节点数202020Floyd-Warshall\texttt{Floyd-Warshall}Floyd-WarshallO(203)8000O(20^3) 8000O(203)8000可接受。代码实现// Risk// UVa ID: 567// Verdict: Accepted// Submission Date: 2016-08-10// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;while(true){intcountry[21][21]{0};intborders,edge,start,end;for(inti1;i20;i)for(intj1;j20;j)country[i][j]100000;boolreadedtrue;for(inti1;i19;i){if(cinborders){for(intj1;jborders;j){cinedge;country[i][edge]1;country[edge][i]1;}}else{readedfalse;break;}country[i][i]0;}if(readedfalse)break;coutTest Set #cases\n;for(intk1;k20;k)for(inti1;i20;i)for(intj1;j20;j)if(country[i][k]country[k][j]country[i][j])country[i][j]country[i][k]country[k][j];cinborders;for(inti1;iborders;i){cinstartend;coutsetw(2)start to setw(2)end: country[start][end]\n;}cout\n;}return0;}