第k短路

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #define mt(a,b) memset(a,b,sizeof(a))
  6 using namespace std;
  7 const int inf=0x3f3f3f3f;
  8 class AStar { ///A*+spfa求第k短路
  9     typedef int typec;///边权的类型
 10     static const int ME=1e5+10;///边的个数
 11     static const int MV=1e3+10;///点的个数
 12     struct G {
 13         struct E {
 14             int v,next;
 15             typec w;
 16         } e[ME];
 17         int le,head[MV];
 18         void init(int n) {
 19             le=0;
 20             for(int i=0; i<=n; i++) head[i]=-1;
 21         }
 22         void add(int u,int v,typec w) {
 23             e[le].v=v;
 24             e[le].w=w;
 25             e[le].next=head[u];
 26             head[u]=le++;
 27         }
 28     };
 29     class Spfa { ///单源最短路o(k*ME)k~=2
 30         G g;
 31         int n,inque[MV],i,u,v;
 32         typec dist[MV];
 33         bool used[MV];
 34         queue<int> q;
 35     public:
 36         void init(int tn) { ///传入点的个数
 37             n=tn;
 38             g.init(n);
 39         }
 40         void add(int u,int v,typec w) {
 41             g.add(u,v,w);
 42         }
 43         bool solve(int s) { ///传入起点,存在负环返回false
 44             for(i=0; i<=n; i++) {
 45                 dist[i]=inf;
 46                 used[i]=true;
 47                 inque[i]=0;
 48             }
 49             used[s]=false;
 50             dist[s]=0;
 51             inque[s]++;
 52             while(!q.empty()) q.pop();
 53             q.push(s);
 54             while(!q.empty()) {
 55                 u=q.front();
 56                 q.pop();
 57                 used[u]=true;
 58                 for(i=g.head[u]; ~i; i=g.e[i].next) {
 59                     v=g.e[i].v;
 60                     if(dist[v]>dist[u]+g.e[i].w) {
 61                         dist[v]=dist[u]+g.e[i].w;
 62                         if(used[v]) {
 63                             used[v]=false;
 64                             q.push(v);
 65                             inque[v]++;
 66                             if(inque[v]>n) return false;
 67                         }
 68                     }
 69                 }
 70             }
 71             return true;
 72         }
 73         typec getdist(int id) {
 74             return dist[id];
 75         }
 76     } spfa;
 77     struct Q {
 78         int p;
 79         typec g,h;
 80         friend bool operator <(const Q &a,const Q &b) {
 81             return a.g+a.h>b.g+b.h;
 82         }
 83     } now,pre;
 84     priority_queue<Q> q;
 85     int n,cnt[MV];
 86     G g;
 87     typec ans;
 88 public:
 89     void init(int tn) {
 90         n=tn;
 91         g.init(n);
 92         spfa.init(n);
 93     }
 94     void add(int u,int v,typec w) {
 95         g.add(u,v,w);
 96         spfa.add(v,u,w);
 97     }
 98     bool solve(int s,int t,int k) {
 99         if(s==t) k++;
100         spfa.solve(t);
101         while (!q.empty()) q.pop();
102         for(int i=0; i<=n; i++) cnt[i]=0;
103         now.p=s;
104         now.g=0;
105         now.h=0;
106         q.push(now);
107         while(!q.empty()) {
108             pre=q.top();
109             q.pop();
110             int u=pre.p;
111             cnt[u]++;
112             if(cnt[u]==k&&u==t) {
113                 ans=pre.h+pre.g;
114                 return true;
115             }
116             if(cnt[u]>k) continue;
117             for(int i=g.head[u]; ~i; i=g.e[i].next) {
118                 now.h=pre.h+g.e[i].w;
119                 int v=g.e[i].v;
120                 now.g=spfa.getdist(v);
121                 now.p=v;
122                 q.push(now);
123             }
124         }
125         return false;
126     }
127     typec getans() {
128         return ans;
129     }
130 } gg;
131 int main() {
132     int n,m,u,v,w,s,t,k;
133     while(~scanf("%d%d",&n,&m)) {
134         gg.init(n);
135         while(m--) {
136             scanf("%d%d%d",&u,&v,&w);
137             gg.add(u,v,w);
138         }
139         scanf("%d%d%d",&s,&t,&k);
140         if(!gg.solve(s,t,k)) {
141             puts("-1");
142         } else {
143             printf("%d\n",gg.getans());
144         }
145     }
146     return 0;
147 }