dij单源最短路纯模板

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <cmath>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <set>
11 #include <map>
12 using namespace std;
13 typedef long long LL;
14 const int maxn=2200;
15 const int INF=0x3f3f3f3f;
16 struct Edge
17 {
18     int u, v, d;
19     Edge(int u, int v, int d):u(u), v(v), d(d) {}
20 };
21 
22 struct qnode
23 {
24     int u,d;
25     qnode(int u, int d):u(u), d(d) {}
26     bool operator < (const qnode a)const
27     {
28         return d>a.d;
29     }
30 };
31 
32 struct Dijkstra
33 {
34     int n;
35     vector<int> G[maxn];
36     vector<Edge> edge;
37     long long d[maxn];
38     bool vis[maxn];
39     void init(int n)
40     {
41         this->n=n;
42         for(int i=0; i<=n; i++)
43         {
44             G[i].clear();
45             vis[i]=0;
46             d[i]=INF;
47         }
48         edge.clear();
49     }
50     void AddEdge(int u, int v, int d)
51     {
52         G[u].push_back(edge.size());
53         edge.push_back(Edge(u, v, d));
54     }
55     void dijkstra(int s)
56     {
57         priority_queue<qnode> q;
58         d[s]=0;
59         q.push(qnode(s, 0));
60         while(!q.empty())
61         {
62             qnode x=q.top();
63             q.pop();
64 
65             if(vis[x.u])
66                 continue ;
67             vis[x.u]=true;
68             for(int i=0; i<G[x.u].size(); i++)
69             {
70                 Edge& e=edge[G[x.u][i]];
71                 if(d[e.v]>d[x.u]+e.d)
72                 {
73                     d[e.v]=d[x.u]+e.d;
74                     q.push(qnode(e.v, d[e.v]));
75                 }
76             }
77         }
78     }
79 } dij;
80 
81 int main()
82 {
83     int n, m;
84     while(~scanf("%d%d", &m, &n))
85     {
86         dij.init(n);
87         while(m--)
88         {
89             int u, v, w;
90             scanf("%d%d%d", &u, &v, &w);
91             dij.AddEdge(u, v, w);
92             dij.AddEdge(v, u, w);
93         }
94         dij.dijkstra(n);
95         printf("%I64d
",dij.d[1]);
96     }
97     return 0;
98 }
View Code