当前位置：首页 > news >正文

UVa 567 Risk

news 2026/6/22 14:09:12

题目描述

题目要求计算给定无向图中两点之间的最短路径长度（边数）。图有202020个节点，输入描述了111到191919的每个节点与更高编号节点的连接关系。然后给出若干查询，输出从起点到终点的最短路径边数（包括终点）。

输入格式

输入包含多个测试集。每个测试集前191919行描述图：第iii行（1≤i≤191 \le i \le 191≤i≤19）包含一个整数XXX，表示与节点iii相邻的更高编号节点数，然后XXX个整数JJJ（i<J≤20i < J \le 20i<J≤20）。第202020行是一个整数NNN（1≤N≤1001 \le N \le 1001≤N≤100），表示查询数。接下来NNN行，每行两个整数AAA、BBB（1≤A,B≤201 \le A, B \le 201≤A,B≤20，A≠BA \ne BA=B），表示起点和终点。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个测试集，输出Test Set #T（TTT从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]，i=ji = ji=j时为000，有边时为111，否则为∞\infty∞。
运行Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法，得到任意两点间最短路径长度。
对于每个查询，直接输出结果。

复杂度分析

节点数202020，Floyd-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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;while(true){intcountry[21][21]={0};intborders,edge,start,end;for(inti=1;i<=20;i++)for(intj=1;j<=20;j++)country[i][j]=100000;boolreaded=true;for(inti=1;i<=19;i++){if(cin>>borders){for(intj=1;j<=borders;j++){cin>>edge;country[i][edge]=1;country[edge][i]=1;}}else{readed=false;break;}country[i][i]=0;}if(readed==false)break;cout<<"Test Set #"<<++cases<<'\n';for(intk=1;k<=20;k++)for(inti=1;i<=20;i++)for(intj=1;j<=20;j++)if(country[i][k]+country[k][j]<country[i][j])country[i][j]=country[i][k]+country[k][j];cin>>borders;for(inti=1;i<=borders;i++){cin>>start>>end;cout<<setw(2)<<start<<" to "<<setw(2)<<end<<": "<<country[start][end]<<'\n';}cout<<'\n';}return0;}