点击打开链接uva 567
1思路:最短路+floyd
2分析:题目给定的点的个数为20,那么根据f'loyd的时间复杂度不会超时,那么直接利用floyd即可。
3注意输出的格式问题
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 25
#define INF 0xFFFFFFF
int n , cnt;
long long dis[MAXN][MAXN];
/*初始化dis数组*/
void init(){
for(int i = 1 ; i <= 20 ; i++){
for(int j = 1 ; j <= 20 ; j++){
if(i == j)
dis[i][j] = 0;
else
dis[i][j] = INF;
}
}
}
/*求最小值函数*/
long long min(long long a , long long b){
return a < b ? a : b;
}
/*floyd算法*/
void floyd(){
int a , b;
for(int k = 1; k <= 20 ; k++){
for(int i = 1 ; i <= 20 ; i++){
for(int j = 1 ; j <= 20 ; j++)
dis[i][j] = min(dis[i][j] , dis[i][k]+dis[k][j]);
}
}
scanf("%d" , &n);
printf("Test Set #%d\n" , cnt++);
for(int i = 1 ; i <= n ; i++){
scanf("%d%d" , &a , &b);
printf("%2d to %2d: %lld\n" , a , b , dis[a][b]);/*输出问题*/
}
printf("\n");
}
int main(){
//freopen("input.txt" , "r" , stdin);
int x , a;
cnt = 1;
while(scanf("%d" , &x) != EOF){
init();
for(int i = 1 ; i <= x ; i++){
scanf("%d" , &a);
dis[1][a] = dis[a][1] = 1;
}
for(int i = 2 ; i <= 19 ; i++){
scanf("%d" , &x);
for(int j = 1 ; j <= x ; j++){
scanf("%d" , &a);
dis[i][a] = dis[a][i] = 1;
}
}
floyd();
}
return 0;
}
分享到:
相关推荐
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
PDF试题
UVA 499 Solution in C/ C++