时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
万圣节的中午，小Hi和小Ho在吃过中饭之后，来到了一个新的鬼屋！
鬼屋中一共有N个地点，分别编号为1..N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。
由于没有肚子的压迫，小Hi和小Ho决定好好的逛一逛这个鬼屋，逛着逛着，小Hi产生了这样的问题：鬼屋中任意两个地点之间的最短路径是多少呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，分别表示鬼屋中地点的个数和道路的条数。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^2，M<=10^3, 1 <= length_i <= 10^3。
对于100%的数据，满足迷宫中任意两个地点都可以互相到达。
输出
对于每组测试数据，输出一个N*N的矩阵A，其中第i行第j列表示，从第i个地点到达第j个地点的最短路径的长度，当i=j时这个距离应当为0。
- 样例输入
-
5 121 2 9672 3 9003 4 7714 5 1962 4 7883 1 6371 4 8832 4 825 2 6471 4 1982 4 1815 2 665
样例输出 -
0 280 637 198 394 280 0 853 82 278 637 853 0 771 967 198 82 771 0 196 394 278 967 196 0
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int N, M; 8 vector > graph; 9 10 void solve() {11 for (int k = 1; k <= N; ++k) {12 for (int i = 1; i <= N; ++i) {13 for (int j = 1; j <= N; ++j) {14 if (graph[i][k] < INT_MAX && graph[k][j] < INT_MAX) {15 graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);16 }17 }18 }19 }20 for (int i = 1; i <= N; ++i) {21 for (int j = 1; j <= N; ++j) {22 cout << graph[i][j] << " ";23 }24 cout << endl;25 }26 }27 28 int main() {29 while (cin >> N >> M) {30 graph.assign(N+1, vector (N+1, INT_MAX));31 for (int i = 1; i <= N; ++i) {32 graph[i][i] = 0;33 }34 int u, v, len;35 for (int i = 1; i <= M; ++i) {36 cin >> u >> v >> len;37 graph[u][v] = graph[v][u] = min(graph[u][v], len);38 }39 solve();40 }41 return 0;42 }
