poj2387Til the Cows Come Home（dijkstra）

优先队列+链星优化的dijkstra。
 1 #include<cstring>
 2 #include<algorithm>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn=1050;
 6 const int maxe=5100;
 7 int t,n;
 8 int head[maxn];
 9 int dis[maxn];
10 typedef pair<int,int> P;
11 struct node
12 {
13     int v,w,nex;
14 }edge[maxe];
15 
16 int cnt;
17 
18 void add(int u,int v,int w)
19 {
20     edge[cnt].v=v;
21     edge[cnt].w=w;
22     edge[cnt].nex=head[u];
23     head[u]=cnt++;
24 }
25 int dijkstra()
26 {
27     priority_queue<P,vector<P>,greater<P> > pq;
28     P p;
29     node e;
30     int v;
31     for(int i=0;i<=n;i++)
32         dis[i]=999999;
33     dis[n]=0;
34     pq.push(P(0,n));
35        while(!pq.empty())
36         {
37             p=pq.top();
38             pq.pop();
39             v=p.second;
40             if(dis[v]<p.first) continue;
41             for(int i=head[v];i!=-1;i=edge[i].nex)
42             {
43                 e=edge[i];
44                 if(dis[e.v]>e.w+dis[v])
45                 {
46                     dis[e.v]=e.w+dis[v];
47                     pq.push(P(dis[e.v],e.v));
48                 }
49             }
50         }
51         printf("%d
",dis[1]);
52 }
53 int main()
54 {
55     while(scanf("%d%d",&t,&n)!=EOF)
56     {
57         cnt=0;
58         int u,v,w;
59         memset(head,-1,sizeof(head));
60         while(t--)
61         {
62             scanf("%d%d%d",&u,&v,&w);
63             add(u,v,w);
64             add(v,u,w);
65         }
66         dijkstra();
67 
68     }
69 }