最短路模板。选迪杰。
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 #include<queue> 6 //#include<iostream> 7 using namespace std; 8 9 int n,m,s,t; 10 #define maxn 2511 11 #define maxm 12411 12 const int inf=0x3f3f3f3f; 13 struct Graph 14 { 15 struct Edge{int to,v,next;}edge[maxm];int first[maxn],le; 16 Graph() {memset(first,0,sizeof(first));le=2;} 17 void in(int x,int y,int v) {Edge &e=edge[le];e.to=y;e.v=v;e.next=first[x];first[x]=le++;} 18 void insert(int x,int y,int v) {in(x,y,v);in(y,x,v);} 19 int dis[maxn];bool vis[maxn]; 20 struct qnode 21 { 22 int id,v; 23 bool operator < (const qnode &b) const {return v<b.v;} 24 bool operator > (const qnode &b) const {return v>b.v;} 25 }; 26 priority_queue<qnode,vector<qnode>,greater<qnode> > q; 27 void dijkstra(int s) 28 { 29 for (int i=1;i<=n;i++) dis[i]=inf; 30 memset(vis,0,sizeof(vis)); 31 q.push((qnode){s,0}); 32 while (!q.empty()) 33 { 34 const int x=q.top().id,d=q.top().v;q.pop(); 35 if (vis[x]) continue; 36 vis[x]=1;dis[x]=d; 37 for (int i=first[x];i;i=edge[i].next) 38 { 39 const Edge &e=edge[i]; 40 if (dis[e.to]>d+e.v) 41 { 42 dis[e.to]=d+e.v; 43 q.push((qnode){e.to,dis[e.to]}); 44 } 45 } 46 } 47 } 48 }g; 49 int x,y,v; 50 int main() 51 { 52 scanf("%d%d%d%d",&n,&m,&s,&t); 53 for (int i=1;i<=m;i++) 54 { 55 scanf("%d%d%d",&x,&y,&v); 56 g.insert(x,y,v); 57 } 58 g.dijkstra(s); 59 printf("%d ",g.dis[t]); 60 return 0; 61 }