cf 20C Dijkstra?

带队列  dijkstra

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <vector>

 #include<memory.h>

 #include<algorithm>//reverse

 using namespace std;

 #define maxn 100002

 #define INF 65

 struct node

 {

     int u;

     int w;

     node(long long x,long long y)

     {

         u = x;

         w = y;

     }

     bool operator < ( const node& p ) const

     {      return w > p.w;   }

 };

 vector<long long>g[maxn];

 vector<long long>cost[maxn];

 long long d[maxn];

 long long par[maxn];

 int dijk(int n)

 {

     memset(d, INF, sizeof(d));

     memset(par, -, sizeof(par));

     priority_queue<node>q;

     q.push(node(,));

     d[]=;

     while(!q.empty())

     {

         node top = q.top();

         q.pop();

         int uu = top.u;

         if(uu == n) return d[n];

         for(int i = ;i < g[uu].size(); i++)

         {

             int v = g[uu][i];

             if(d[uu] + cost[uu][i] < d[v])

             {

                 d[v] = d[uu] + cost[uu][i];

                 par[v] = uu;

                 q.push(node(v,d[v]));

             }

         }

     }

     return -;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     int n,e,u,v;

     long long w;

     cin>>n>>e;

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

     {

         cin>>u>>v>>w;

         g[u].push_back(v);cost[u].push_back(w);

         g[v].push_back(u);cost[v].push_back(w);

     }

     w = dijk(n);

     if(w == -) cout<<"-1"<<endl;

     else

     {

         int t = n;

         int s[maxn];

         int k = ;

         while(t != -)

         {

             s[k++] = t;

             t = par[t];

         }

         for(int j = k - ; j >= ; j--)

             cout<<s[j]<<" ";

         cout<<endl;

     }

 }