1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 #include<cstring> 5 #include<vector> 6 #define MAXN 222 7 struct edge { 8     int k,w; 9     bool operator < (const edge &b)const//the order to sort elements in priority queue10     {11         return w > b.w;12     }13     edge(int kk = 0, int ww = 0)// Constructor14     {15         k = kk;16         w = ww;17     }18 };19 int N, M, A, B, X, S, T;20 std::vector< std::vector<edge> > G;//a vector in a vector21 //while you use vector , you don‘t have to create a 2d array, avoid wasting the memory.22 bool vis[MAXN];23 24 int dijkstra(int s, int t)25 {26     std::priority_queue<edge> q;27     edge head(s,0),node;28     q.push(head);29     while(q.empty()==false) {30         head = q.top();//get the element at the front of the priority queue31         q.pop();//the delete it32         vis[head.k] = true;//a tag ,this element has been visited, we have get the shortest way from source to it33         if(head.k == t)34             return head.w;35         for(int i = 0; i<G[head.k].size(); i++) {//36             node.k = G[head.k][i].k;37             if(vis[node.k]==true)//if the point has been reached , skip it.38                 continue;39             node.w = G[head.k][i].w + head.w;40              q.push(node);//the newly extended point41         }42     }43     return -1;//can not find a way till every element have been visited.44 // So there is no way from source to sink45 }46 47 int main()48 {49 //    freopen("in.txt","r",stdin);50     while(~scanf("%d%d",&N,&M)) {51         memset(vis,false,sizeof(vis));52         G.clear();53         G.resize(MAXN);54         while(M--) {55             scanf("%D%D%D",&A,&B,&X);56             edge temp;57             temp.k = B;58             temp.w = X;59             G[A].push_back(temp);//two-way road here60             temp.k = A;61             G[B].push_back(temp);62         }63         scanf("%d%d",&S,&T);64         printf("%d\n",dijkstra(S, T));65     }66 }