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; }