1 #include <iostream> 2 #include <queue> 3 #include <vector> 4 using namespace std; 5 const int N=405; 6 struct rec 7 { 8 int v,w; 9 }; 10 vector<rec> edge[N*N]; 11 int n,st,ed; 12 __int64 dis[N*N]; 13 bool vis[N*N]; 14 struct cmp 15 { 16 bool operator()(int a,int b) 17 { 18 return dis[a]>dis[b]; 19 } 20 }; 21 void Dijkstra() 22 { 23 priority_queue<int,vector<int>,cmp> Q; 24 memset(dis,-1,sizeof(dis)); 25 memset(vis,0,sizeof(vis)); 26 int i,u,v; 27 Q.push(st); 28 dis[st]=0; 29 while(!Q.empty()) 30 { 31 u=Q.top(); 32 Q.pop(); 33 vis[u]=0; 34 if(u==ed) 35 break; 36 for(i=0;i<edge[u].size();i++) 37 { 38 v=edge[u][i].v; 39 if(dis[v]==-1 || dis[v]>dis[u]+edge[u][i].w) 40 { 41 dis[v]=dis[u]+edge[u][i].w; 42 if(!vis[v]) 43 { 44 vis[v]=1; 45 Q.push(v); 46 } 47 } 48 } 49 } 50 }