链式前向星

学习链式前向星：http://blog.csdn.net/acdreamers/article/details/16902023
留个链式前向星+Dijkstra模板。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 #define next Next
 8 const int maxn = 1e3+50;
 9 const int inf = 0x3f3f3f3f;
10 
11 struct Edge
12 {
13     int to;
14     int w;
15     int next;        ///以i为起点，该条边的下一条
16     friend bool operator < (Edge A,Edge B)
17     {
18         return A.w>B.w;
19     }
20 };
21 int cnt;
22 int head[maxn];     ///表示以i为起点的边的最大编号，逆序来
23 int vis[maxn];
24 int d[maxn];
25 Edge e[maxn*2];   ///双向边
26 void init()
27 {
28     memset(head,-1,sizeof(head));
29     cnt = 0;
30 }
31 void addedge(int u,int v,int w)
32 {
33     e[cnt].to = v;
34     e[cnt].w = w;
35     e[cnt].next = head[u];
36     head[u] = cnt++;
37 }
38 void dijkstra(int s)
39 {
40     memset(vis,0,sizeof(vis));
41     memset(d,inf,sizeof(d));
42     d[s] = 0;
43     priority_queue<Edge> q;
44     q.push((Edge){s,0});
45     while(!q.empty())
46     {
47         Edge cur = q.top();
48         int u = cur.to;
49         q.pop();
50         if(vis[u]) continue;
51         vis[u] = 1;
52         for(int i=head[u];~i;i=e[i].next)
53         {
54             int v = e[i].to;
55             if(d[v]>d[u]+e[i].w)
56             {
57                 d[v] = d[u]+e[i].w;
58                 q.push((Edge){v,d[v]});
59             }
60         }
61     }
62 }
63 int main()
64 {
65     int n,m;
66     while(scanf("%d %d",&n,&m)!=EOF)
67     {
68         init();
69         int a,b,x;
70         for(int i=1;i<=m;i++)
71         {
72             scanf("%d %d %d",&a,&b,&x);
73             addedge(a,b,x);
74             addedge(b,a,x);
75         }
76         int s,t;
77         scanf("%d %d",&s,&t);
78         dijkstra(s);
79         if(d[t]!=inf)
80         printf("%d
",d[t]);
81         else puts("-1");
82     }
83     return 0;
84 }