哈理工oj 1348 最短路径（floyd算法）

最短路径 Time Limit: 1000 MS Memory Limit: 32767 K Total Submit: 208(28 users) Total Accepted: 31(20 users) Rating: Special Judge: No Description 给出一个有向带权图G，针对该图有如下的两种操作：（1）标记该图的一个点（2）找到两点间的只通过已标记点的最短路径长度输入：输入包括多组测试，每组测试中第一行包括三个整数N，M，Q，N表示图中的节点数量，，N<=300，M表示边的数量，M<=100000;Q表示执行多少次操作，Q<=100000，所有点被编号为0,1,2,…,N-1，最初所有的点都是未标记的，接下来M行每行包括三个整数x,y,c,表示从x到y有一条边长度为c,c>0，然后为Q行，每行表示一次操作，0 x表示将点x标记，1 x y表示查找x到y的只通过已标记点的最短路径长度，N=M=Q=0是输入结束。输出：输出以一行"Case #:"开始，#表示为第几组测试，从1开始对于0 x操作，如果x已经被标记过了，输出"ERROR! At point x".对于1 x y操作，如果x或y没有被标记过，输出"ERROR! At path x to y"，如果无法从x通过标记过的节点到达y,输出"No such path"，否则输出要求的最短路径长度，每组测试后有一个空行。 Input 输入包括多组测试，每组测试中第一行包括三个整数N，M，Q，N表示图中的节点数量，N<=300，M表示边的数量，M<=100000;Q表示执行多少次操作，Q<=100000，所有点被编号为0,1,2,…,N-1，最初所有的点都是未标记的，接下来M行每行包括三个整数x,y,c,表示从x到y有一条边长度为c,c>0，然后为Q行，每行表示一次操作，0 x表示将点x标记，1 x y表示查找x到y的只通过已标记点的最短路径长度，N=M=Q=0是输入结束。 Output 输出以一行"Case #:"开始，#表示为第几组测试，从1开始对于0 x操作，如果x已经被标记过了，输出"ERROR! At point x".对于1 x y操作，如果x或y没有被标记过，输出"ERROR! At path x to y"，如果无法从x通过标记过的节点到达y,输出"No such path"，否则输出要求的最短路径长度，每两组测试之间有一个空行。 Sample Input 5 10 101 2 63350 4 57253 3 69634 0 81461 2 99621 0 19432 1 23924 2 1542 2 74221 3 98960 10 30 20 40 40 11 3 31 1 10 30 40 0 0 Sample Output Case 1: ERROR! At point 4 ERROR! At point 1 0 0 ERROR! At point 3 ERROR! At point 4 要懂得floyd算法原理，对每个顶点所有边都要松弛一遍，那么这是在所有边都可访问的情况下。对于这个题目，可以每次标记一个点，都以这个点为中心松弛所有边 [cpp] view plaincopy #include<iostream>#include<string.h>using namespace std;const int INF=304;int G[INF][INF];int vis[INF];int main(){int n,m,q;int u,v,w,cse=1;while(cin>>n>>m>>q,n+m+q){memset(G,0x1f,sizeof(G));memset(vis,0,sizeof(vis));for(int i=0; i<=n; i++)G[i][i]=0;for(int i=0; i<m; i++){cin>>u>>v>>w;G[u][v]=G[u][v]>w?w:G[u][v];}cout<<"Case "<<cse++<<":\n";int x,y,z;for(int i=0; i<q; i++){cin>>x;if(x){cin>>y>>z;if(!vis[y]||!vis[z]){cout<<"ERROR! At path "<<y<<" to "<<z<<endl;}else if(G[y][z]>=0x1f1f1f1f){cout<<"No such path"<<endl;}elsecout<<G[y][z]<<endl;}else{cin>>y;if(vis[y]){cout<<"ERROR! At point "<<y<<endl;}else{vis[y]=1;for(int i=0; i<n; i++){for(int j=0; j<n; j++){if(G[i][y]+G[y][j]<G[i][j]){G[i][j]=G[i][y]+G[y][j];}}}}}}cout<<endl;}return 0;}

我知道有一种爱情，叫做与你白头，有一种幸福，叫做和你相伴。

相关文章：

你感兴趣的文章：

标签云：