http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=508
题目大意:给定20个点,以及一些连接这些点的边,然后多次任意给定两点,求起始点到终点所经过的最少边数。
题目分析:此题可以把图看作是一个所有权值均为1的带权无向图,即求任意顶点之间的最短路问题,用Floyd算法。
由于此题的数据量很少,所以直接用bfs也可。
代码:
//权值均为1的多源最短路问题
//可以用bfs,由于需要多次查询,故效率不高
//可以用floyd算法,O(n^3),查询为O(1)
#include
#include
#include
#define INF 100000
using namespace std;
const int maxn=50;
int adj[maxn][maxn];//邻接矩阵
int d[maxn][maxn];//记录距离
int main()
{
int k,u,v;
int c=0;
while(cin>>k)
{
c++;
printf("Test Set #%d\n",c);
memset(adj,0,sizeof(adj));
int i=0;
while(k--)
{
cin>>u;
u--;
adj[u][i]=1;
adj[i][u]=1;
}
int j;
for(j=1;j>k;
while(k--)
{
cin>>u;
u--;
adj[u][i]=1;
adj[i][u]=1;
}
}
for(i=0;i>n;
for(i=1;i>u>>v;
printf("%2d to %2d:%2d\n",u,v,d[u-1][v-1]);
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
uva最全ac代码
在 Python 3 中解决了一些 UVA 问题
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
UVA 题目,不是很难,试试吧
uva357的栈实现版本
uva10755 ac 代码,可以随意更改下载
《算法竞赛入门经典》UVa配套题目pdf版完整
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
uva_trilearn2002 源代码
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
主要是uvaoj习题相关题目 练习题目
UVA 499 Solution in C/ C++