dij单源最短路纯模板

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 #include <queue>

 #include <stack>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 const int maxn=;

 const int INF=0x3f3f3f3f;

 struct Edge

 {

     int u, v, d;

     Edge(int u, int v, int d):u(u), v(v), d(d) {}

 };

 struct qnode

 {

     int u,d;

     qnode(int u, int d):u(u), d(d) {}

     bool operator < (const qnode a)const

     {

         return d>a.d;

     }

 };

 struct Dijkstra

 {

     int n;

     vector<int> G[maxn];

     vector<Edge> edge;

     long long d[maxn];

     bool vis[maxn];

     void init(int n)

     {

         this->n=n;

         for(int i=; i<=n; i++)

         {

             G[i].clear();

             vis[i]=;

             d[i]=INF;

         }

         edge.clear();

     }

     void AddEdge(int u, int v, int d)

     {

         G[u].push_back(edge.size());

         edge.push_back(Edge(u, v, d));

     }

     void dijkstra(int s)

     {

         priority_queue<qnode> q;

         d[s]=;

         q.push(qnode(s, ));

         while(!q.empty())

         {

             qnode x=q.top();

             q.pop();

             if(vis[x.u])

                 continue ;

             vis[x.u]=true;

             for(int i=; i<G[x.u].size(); i++)

             {

                 Edge& e=edge[G[x.u][i]];

                 if(d[e.v]>d[x.u]+e.d)

                 {

                     d[e.v]=d[x.u]+e.d;

                     q.push(qnode(e.v, d[e.v]));

                 }

             }

         }

     }

 } dij;

 int main()

 {

     int n, m;

     while(~scanf("%d%d", &m, &n))

     {

         dij.init(n);

         while(m--)

         {

             int u, v, w;

             scanf("%d%d%d", &u, &v, &w);

             dij.AddEdge(u, v, w);

             dij.AddEdge(v, u, w);

         }

         dij.dijkstra(n);

         printf("%I64d\n",dij.d[]);

     }

     return ;

 }