/* ------------------------------------------------- Author: wry date: 2022/2/26 21:56 Description: Dijkstra ------------------------------------------------- */ #include <bits/stdc++.h> using namespace std; const int MAXN = 200; struct Edge { int to; int length; Edge(int t,int l):to(t),length(l){} }; struct Point { int id; int distance; Point(int n,int d):number(n),distance(d){} bool operator< (Point p) const{ return distance>p.distance; //距离越小,优先级越高 } }; vector<Edge> graph[MAXN]; int dis[MAXN]; //表示起点到此测试点的最短距离 void Disjkstra(int start,int n) { fill(dis,dis+n,INT_MAX); dis[start] = 0; priority_queue<Point> myPriorityQueue; myPriorityQueue.push(Point(start,dis[start])); //存入第一个点,即它自己 while (!myPriorityQueue.empty()) { int p = myPriorityQueue.top().id; myPriorityQueue.pop(); for (int i=0;i<graph[p].size();i++) { //p _l_> q int q = graph[p][i].to; int l = graph[p][i].length; if (dis[p]+l<dis[q]) { //看是直接到q近还是经过p中转近 dis[q] = dis[p]+l; myPriorityQueue.push(Point(q,dis[q])); } } } } int main() { int n,m; while (cin>>n>>m) { memset(graph,0,sizeof(graph)); //初始化结构体的向量 while (m--) { int from,to,length; cin >> from >> to >> length; //Dijkstra应用于无向图 graph[from].push_back(Edge(to,length)); graph[to].push_back(Edge(from,length)); } int start,end; cin >> start >> end; Disjkstra(start,n); if (dis[end]==INT_MAX) { dis[end] = -1; } } return 0; }