UVA 其实挺折腾的，题目超长，然后题意可能很水，输入输出又奇葩，当做是磨练
其实是最短路径的裸题。固定有20个点点，输入分为两部分，前部分有19行，每一行先输出一个n，表示这行有n个数字，然后输入n个数字。第i行输出的数字v表示i和v之间有边而且是无向边，所有边的权值都是1。
输入的后部分是先输入一个m，表示有m个查询，下面m行输入点u，v输出两点间的最短路径
显然就是Floy算法的裸题。但是新学了spafa，把spfa也放上来
注意的是有20个点从1标号到20，但是输入只有19行，再者就是输出的格式也要注意，本题1Y，当做是练手啦
SPFA
//先给出spafa算法 //这个代码中是得到了邻接矩阵后再输入m个查询 //每得到一个查询进行一次spfa，时间比后面的floy慢了很多 //并不是算法的效率问题，而是数据中有多个重复的查询 //所以为了提高速度可以再得到邻接矩阵后先循环调用一次spfa //得到任意两个顶点的最短路，那么查询的时候直接输出即可 //不过临时写的就没有这样做了，要实现不难，把d数组改为二维即可 #include <cstdio> #include <cstring> #include <queue> using namespace std; #define N 25 //固定是20个点 #define INF 1000000000 int g[N][N]; //邻接矩阵 int d[N]; //单源最短路径 bool vis[N]; //标记那些点已经在队列中 queue <int> q; int input() { int n,v; for(int i=1; i<=20; i++) for(int j=1; j<=20; j++) g[i][j]=INF; if(scanf("%d",&n)==EOF) return 0; for(int i=1; i<=n; i++) { scanf("%d",&v); g[1][v]=g[v][1]=1; } for(int i=2; i<=19; i++) { scanf("%d",&n); for(int j=1; j<=n; j++) { scanf("%d",&v); g[i][v]=g[v][i]=1; } } /* for(int i=1; i<=20; i++) { for(int j=1; j<=20; j++) if(g[i][j]==1) printf("1 "); else printf("* "); printf("\n"); } */ return 1; } void spfa(int s) //得到源点s { memset(vis,0,sizeof(vis)); for(int i=1; i<=20; i++) d[i]=INF; //初始化 d[s]=0; //源点最短路为0 while(!q.empty()) q.pop(); q.push(s); //源点入队 vis[s]=1; //标记已经在队中的元素 while(!q.empty()) { int u; u=q.front(); //读取队头元素 q.pop(); //队头元素出队 vis[u]=0; //要记得清楚标记 //对与点u相连的所有点v都进行松弛操作，如果有改变点v的估计值，那么点v入队 for(int v=1; v<=20; v++) //扫描邻接矩阵中的u行 if( d[u]+g[u][v] < d[v] ) //可以更新d[v] { d[v]=d[u]+g[u][v]; if(!vis[v]) //点v又不在队列中 { q.push(v); //点v入队 vis[v]=1; //记得标记 } } } /* for(int i=1; i<=20; i++) printf("%d ",d[i]); printf("\n"); */ return ; } int main() { int T=0; while(1) { if(!input()) break; T++; int m; printf("Test Set #%d\n",T); scanf("%d",&m); //读入m个查询 for(int i=1; i<=m; i++) //处理m个查询 { int u,v; scanf("%d%d",&u,&v); spfa(u); printf("%2d to %2d: %d\n",u,v,d[v]); } printf("\n"); } return 0; }
Floy
#include <stdio.h> #include <string.h> #define INF 1000000000 #define N 25 int d[N][N]; void Floy() { int i,j,k; for(k=1; k<=20; k++) for(i=1; i<=20; i++) for(j=1; j<=20; j++) if(d[i][j] > d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; return ; } int main() { int T=0; int i,j,n,m,u,v; while(scanf("%d",&n)!=EOF) { T++; for(i=1; i<=20; i++) for(j=1; j<=20; j++) if(i==j) d[i][j]=0; else d[i][j]=INF; for(i=1 ;i<=n; i++) { scanf("%d",&v); d[1][v]=d[v][1]=1; } for(u=2; u<=19; u++) { scanf("%d",&n); while(n--) { scanf("%d",&v); d[u][v]=d[v][u]=1; } } Floy(); printf("Test Set #%d\n",T); scanf("%d",&m); //m给个查询 for(i=1; i<=m; i++) { scanf("%d%d",&u,&v); printf("%2d to %2d: %d\n",u,v,d[u][v]); } printf("\n"); } return 0; }