POJ 2449 Remmarguts' Date

Remmarguts' Date

k短路模板
  1 #include<queue>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxn=1005;
  7 int n,m,s,t,k,num,head1[maxn],head2[maxn],dis[maxn],nxt1[maxn*100],nxt2[maxn*100],cnt;
  8 queue<int>q; bool vis[maxn];
  9 struct Edge{
 10     int u,v,d;
 11 }edge1[maxn*100],edge2[maxn*100];
 12 
 13 struct Data{
 14     int h,g,num;
 15     bool operator < (const Data x) const
 16     {
 17         if(h==x.h) return g>x.g;
 18         return h>x.h;
 19     }
 20 };
 21 
 22 char ch;
 23 inline void read(int &now)
 24 {
 25     ch=getchar(); now=0;
 26     while(ch>'9'||ch<'0') ch=getchar();
 27     while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
 28 }
 29 
 30 void add_Edge(int u,int v,int d)
 31 {
 32     edge2[++num].u=u;
 33     edge2[num].v=v;
 34     edge2[num].d=d;
 35     nxt2[num]=head2[u];
 36     edge1[num].u=v;
 37     edge1[num].v=u;
 38     edge1[num].d=d;
 39     nxt1[num]=head1[v];
 40     head2[u]=num;
 41     head1[v]=num;
 42 }
 43 
 44 void spfa()
 45 {
 46     for(int i=0;i<=n;i++) dis[i]=0x7f;
 47     dis[t]=0;
 48     vis[t]=1;
 49     q.push(t);
 50     while(!q.empty())
 51     {
 52         int cur=q.front(); q.pop();
 53         for(int i=head2[cur];i;i=nxt2[i])
 54         {
 55             int v=edge2[i].v;
 56             if(dis[v]>dis[cur]+edge2[i].d)
 57             {
 58                 dis[v]=dis[cur]+edge2[i].d;
 59                 if(!vis[v])
 60                 {
 61                     vis[v]=1;
 62                     q.push(v);
 63                 }
 64             }
 65         }
 66         vis[cur]=0;
 67     }
 68 }
 69 
 70 int astar()
 71 {
 72     priority_queue<Data>que;
 73     if(s==t) k++;
 74     Data u,v,w;
 75     if(dis[s]==dis[0]) return -1;
 76     u.num=s;
 77     u.g=0;
 78     u.h=dis[s];
 79     que.push(u);
 80     while(!que.empty())
 81     {
 82         v=que.top(); que.pop();
 83         if(v.num==t) cnt++;
 84         if(cnt==k) return v.g;
 85         for(int i=head1[v.num];i;i=nxt1[i])
 86         {
 87             w.num=edge1[i].v;
 88             w.g=v.g+edge1[i].d;
 89             w.h=w.g+dis[edge1[i].v];
 90             que.push(w);
 91         }
 92     }
 93     return -1;
 94 }
 95 
 96 int main()
 97 {
 98     read(n); read(m);
 99     for(int i=1;i<=m;i++)
100     {
101         int x,y,z;
102         read(x); read(y); read(z);
103         add_Edge(y,x,z);
104     }
105     read(s); read(t); read(k);
106     spfa();
107     printf("%d
",astar());
108     return 0;
109 }