1 /* 2 最短路径问题 3 可利用Bellman-Ford算法或者Dijktra算法求解。 4 */ 5 #include <iostream> 6 #include <cstring> 7 #include <vector> 8 #include <queue> 9 using namespace std; 10 const int maxn = 205; 11 const int inf = 0x3f3f3f3f; 12 struct edge 13 { 14 edge(int x,int y) 15 { 16 v = x; 17 len = y; 18 } 19 int v, len; 20 }; 21 vector<edge> e[maxn]; 22 int dis[maxn], inq[maxn]; 23 /*int spfa(int s, int t) //Bellman-Ford 24 { 25 queue<int> q; 26 memset(inq, 0, sizeof inq); 27 memset(dis, 0x3f, sizeof dis); 28 dis[s] = 0; inq[s] = true; 29 q.push(s); 30 while (!q.empty()) 31 { 32 int n = q.front(); 33 q.pop(); 34 for (int i = 0; i < e[n].size(); ++i) 35 { 36 int v = e[n][i].v, len = e[n][i].len; 37 if (dis[v] > dis[n] + len) 38 { 39 dis[v] = dis[n] + len; 40 if (!inq[v]) {q.push(v); inq[v] = true;}//判断队列是否存在该节点，存在无须加入重复判断 41 } 42 } 43 inq[n] = false; 44 } 45 return dis[t]==inf?-1:dis[t]; 46 }*/ 47 int dijktra(int s,int t) //Dijktra 48 { 49 memset(dis,0x3f,sizeof dis); 50 dis[s] = 0; 51 priority_queue< pair<int,int> > q; 52 q.push(make_pair(-dis[s],s)); 53 while(!q.empty()) 54 { 55 int x = -q.top().first,y = q.top().second; 56 q.pop(); 57 if(dis[y] < x) continue;//dis[y] < x表示前面已经储存过更优路径，无需再次更新y后面的节点 58 for(int i = 0; i < e[y].size(); ++i) 59 { 60 int v = e[y][i].v,len = e[y][i].len; 61 if(dis[v] > dis[y] + len) 62 { 63 dis[v] = dis[y] + len; 64 q.push(make_pair(-dis[v],v)); 65 } 66 } 67 } 68 return dis[t]==inf?-1:dis[t]; 69 } 70 int main() 71 { 72 int n, m; 73 while (cin >> n >> m) 74 { 75 for(int i = 0; i < n; ++i) 76 e[i].clear(); 77 for (int i = 0; i < m; ++i) 78 { 79 int x, y, d; 80 cin >> x >> y >> d; 81 e[x].push_back(edge(y,d)); 82 e[y].push_back(edge(x,d)); 83 } 84 int s, t; 85 cin >> s >> t; 86 //int ans = spfa(s,t); 87 int ans = dijktra(s, t); 88 cout << ans << endl; 89 } 90 } 91 /* 92 3 3 93 0 1 1 94 0 2 3 95 1 2 1 96 0 2 97 3 1 98 0 1 1 99 1 2 100 101 */