hdu 6181 Two Paths

题意：问第二短路
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<map>
  7 #include<queue>
  8 #include<stack>
  9 #include<vector>
 10 #include<set>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef pair<ll,int> P;
 14 const int maxn=2e5+100,maxm=2e5+100,inf=0x3f3f3f3f,mod=1e9+7;
 15 const ll INF=1e17+7;
 16 struct edge
 17 {
 18     int from,to;
 19     ll w;
 20 };
 21 vector<edge>G[maxn],T[maxn];
 22 priority_queue<P,vector<P>,greater<P> >q;
 23 ll dist[maxn];
 24 void addedge(int u,int v,ll w)
 25 {
 26     G[u].push_back((edge)
 27     {
 28         u,v,w
 29     });
 30     T[v].push_back((edge)
 31     {
 32         v,u,w
 33     });
 34 }
 35 void dij(int s)
 36 {
 37     dist[s]=0LL;
 38     q.push(P(dist[s],s));
 39     while(!q.empty())
 40     {
 41         P p=q.top();
 42         q.pop();
 43         int u=p.second;
 44         for(int i=0; i<T[u].size(); i++)
 45         {
 46             edge e=T[u][i];
 47             if(dist[e.to]>dist[u]+e.w)
 48             {
 49                 dist[e.to]=dist[u]+e.w;
 50                 q.push(P(dist[e.to],e.to));
 51             }
 52         }
 53     }
 54 }
 55 struct node
 56 {
 57     int to;
 58     ///g(p)为当前从s到p所走的路径的长度;dist[p]为点p到t的最短路的长度;
 59     ll g,f;///f=g+dist,f(p)的意义为从s按照当前路径走到p后再走到终点t一共至少要走多远;
 60     bool operator<(const node &x ) const
 61     {
 62         if(x.f==f) return x.g<g;
 63         return x.f<f;
 64     }
 65 };
 66 
 67 ll A_star(int s,int t,int k)
 68 {
 69     priority_queue<node>Q;
 70     if(dist[s]==INF) return -1;
 71     int cnt=0;
 72     if(s==t) k++;
 73     ll g=0LL;
 74     ll f=g+dist[s];
 75     Q.push((node)
 76     {
 77         s, g, f
 78     });
 79     while(!Q.empty())
 80     {
 81         node x=Q.top();
 82         Q.pop();
 83         int u=x.to;
 84         if(u==t) cnt++;
 85         if(cnt==k) return x.g;
 86         for(int i=0; i<G[u].size(); i++)
 87         {
 88             edge e=G[u][i];
 89             ll g=x.g+e.w;
 90             ll f=g+dist[e.to];
 91             Q.push((node)
 92             {
 93                 e.to, g, f
 94             });
 95         }
 96     }
 97     return -1;
 98 }
 99 void init(int n)
100 {
101     for(int i=0; i<=n+10; i++) G[i].clear(),T[i].clear();
102 }
103 int main()
104 {
105     int t;
106     cin>>t;
107     while(t--)
108     {
109         int n,m;
110         scanf("%d%d",&n,&m);
111         for(int i=1; i<=m; i++)
112         {
113             int u,v;
114             ll w;
115             scanf("%d%d%lld",&u,&v,&w);
116             addedge(u,v,w);
117             addedge(v,u,w);
118         }
119         int s,t,k;
120         //scanf("%d%d%d",&s,&t,&k);
121         for(int i=0; i<=n; i++) dist[i]=INF;
122         dij(n);
123         printf("%lld
",A_star(1,n,2));//s到t的第k短路
124         init(n);
125     }
126     return 0;
127 }