1 #define _CRT_SECURE_NO_WARNINGS 2 /* 3 7 10 4 0 1 5 5 0 2 2 6 1 2 4 7 1 3 2 8 2 3 6 9 2 4 1010 3 5 111 4 5 312 4 6 513 5 6 914 0 615 */16 #include <iostream>17 #include <vector>18 #include <utility>19 #include <queue>20 #include <functional>21 #include <algorithm>22 #include <cstdio>23 using namespace std;24 25 const int maxn = 1010 + 20;26 const int INF = 99999999;27 28 int d[maxn][maxn];         //d[u][v]表示边e=(u,v)的权值(不存在时设为INF,不过d[i][j]=0)29 int V, E;30 31 void input();32 void warshall_floyd();33 void init();34 35 void init() {36     for (int i = 0; i < V; i++) {37         for (int j = 0; j < V; j++) {38             if (i == j) {39                 d[i][j] = 0;40             }41             else {42                 d[i][j] = INF;43             }44         }45     }46 }47 48 void input()49 {50     int s, t, ct;51     for (int i = 0; i < E; i++) {52         cin >> s >> t >> ct;53         d[s][t] = d[t][s] = ct;54     }55 }56 57 void warshall_floyd()58 {59     for (int k = 0; k < V; k++) {         //考虑经过顶点k和不经过顶点k的情况60         for (int i = 0; i < V; i++) {61             for (int j = 0; j < V; j++) {62                 d[i][j] = min(d[i][j], d[i][k] + d[k][j]);63             }64         }65     }66 }67 68 int main()69 {70     cin >> V >> E;71     init();                //必须要初始化72     input();73     warshall_floyd();74     int st, ov;75     cin >> st >> ov;       //输入起点终点76     cout << d[st][ov] << endl;77     return 0;78 }