题意：
给一个无向图，求出两点间的最短距离（这里还要加上每个地点花费cost[i]），并输出路径。
分析：
floyd算法，输出字典序最小路径（lexically smallest ）
注意下特殊情况，到自身情况输出的格式!
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
#define maxn 200
using namespace std;
int n;
int cost[maxn];
int dist[maxn][maxn];
int path[maxn][maxn];
void floyd()
{for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)path[i][j] = j;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)if (dist[i][k] < INF&&dist[k][j] < INF){if (dist[i][j] > dist[i][k] + dist[k][j] + cost[k]){dist[i][j] = dist[i][k] + dist[k][j] + cost[k];path[i][j] = path[i][k];}else if (dist[i][j] == dist[i][k] + dist[k][j] + cost[k] && path[i][j] > path[i][k])path[i][j] = path[i][k];}
}int main()
{while (cin >> n, n){for(int i=1;i<=n;i++)for (int j = 1; j <= n; j++){cin >> dist[i][j];if (dist[i][j] == -1)dist[i][j] = INF;}for (int i = 1; i <= n; i++)cin >> cost[i];floyd();while(1){int u, v;cin >> u >> v; if (u == -1 && v == -1)break;printf("From %d to %d :\n", u,v);if (u != v){printf("Path: %d", u);int beg = path[u][v];while (1){printf("-->%d", beg);if (beg == v) { cout << endl; break; }beg = path[beg][v];}}else printf("Path: %d\n", u);printf("Total cost : %d\n\n", dist[u][v]);}}system("pause");
}