soj2427: Daizi's path system

xiaoxiao2021-02-28  2

soj2427: Daizi's path system

http://acm.scu.edu.cn/soj/problem.action?id=2427

简介题意:n个路口,m条路,找出任意两点间的最短距离,最后k组测试,有就输出距离,没有就pity

这就是Floyd嘛。Floyd就是任意两点间的最小距离嘛。Dijkstra是从原点到所有点的最短嘛。

主题思想就是判断是否 road[i][j] > road[i][k]+road[k][j],有的话说明ij中间有路口k连接两点的路程加起来更短呗。那road[i][j] = road[i][k]+road[k][j],一直到最后就行了。

比较注意的就是这是三重for循环对吧,所以看,i和j改变比较多啊,所以k循环在最外层。ij一样的,随便。

代码如下:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 110 #define INF 0x3f3f3f3f int road[MAX][MAX]; void Floyd(int n) { for(int k = 1; k <= n; k++) for(int i = 1; i <= n ; i++) for(int j = 1; j <= n; j++) if(road[i][j] > road[i][k]+road[k][j]) road[i][j] = road[j][i] = road[i][k] + road[k][j]; } int main() { int n,m; while(~scanf("%d%d",&n,&m)&&n&&m) { memset(road,INF,sizeof(road)); for(int i = 1;i <= m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(road[a][b] > c) { road[a][b] = c; road[b][a] = c; } } for(int i = 1; i <= n; i++) road[i][i] = 0; //对了,这个别忘了,自己到自己是0嘛 Floyd(n); int k; scanf("%d",&k); while(k--) { scanf("%d%d",&n,&m); if(road[n][m] < INF) printf("%d\n",road[n][m]); else printf("pity\n"); } printf("\n"); //这一行让我错了五次,他说“每组”结束输出一行空格,我直接\n\n每次输出都空行了,哎呦崩溃 } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1150331.html

最新回复(0)