提交了N次啊,最后发现是没有处理最后无解输出-1的情况(只有少于K条路径)。
逐一搜索第1短、第2短、第3短。。。的路径,count统计一个点入队的次数。
count[i]>k cut! count[T]=K ans=f[T].
两种无解的情况:1.到不了。2。只有少于k条路(好像都是一种情况。。。)
代码(非提交版)
#include<queue>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
//
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define DFOR(i,r,l) for (int i=(r);i>=(l);i--)
#define NFOR(i,l,r) for (i=(l);i<=(r);i++)
#define NDFOR(i,r,l) for (i=(r);i>=(l);i--)
#define PFOR(p,a,next) for(int p=a;p;p=next[p])
#define NPFOR(p,a,next) for(p=a;p;p=next[p])
//
typedef long long Int64;
const int INF=~0U>>2;
const int maxn=1005;
const int maxm=200005;
//
int head[maxn],next[maxm],to[maxm],w[maxm];
int a[maxm],b[maxm];
int h[maxn];
int Q[maxm],Head,Tail;
int inQ[maxn];
//
class node{
public:
int v,f;
bool operator < (const node &x)const{
return f > x.f;
}
};
priority_queue<node>q;
//
ifstream fin("poj2449.in");
ofstream fout("poj2449.out");
//
int S,T,K;
int n,m;
int main(){
int count[maxn];
fin>>n>>m;
MM(head,0),MM(next,0),MM(to,0),MM(w,0),MM(inQ,false);
FOR(i,1,m)
fin>>a[i]>>b[i]>>w[i],
next[i]=head[b[i]],head[b[i]]=i,to[i]=a[i];
fin>>S>>T>>K;
//make H
FOR(i,1,n)h[i]=INF;
Head=Tail=1;Q[1]=T;h[T]=0;
for(;Head<=Tail;){
int &qq=Q[Head];
PFOR(p,head[qq],next)
if(h[qq]+w[p]<h[to[p]]){
h[to[p]]=h[qq]+w[p];
if(!inQ[to[p]])//这里不是标准的SPFA,对于A*的H,可以近似的处理??
//完了,我又不确定了。。。 标准SPFA 954MS AC 这个版本 235MS AC
Tail++,Q[Tail]=to[p],inQ[to[p]]=true;
}
Head++;
inQ[qq]=false;
}
if(h[S]==INF){fout<<"-1";return 0;}
//find K
MM(head,0),MM(next,0),MM(to,0),MM(count,0);
FOR(i,1,m)
next[i]=head[a[i]],head[a[i]]=i,to[i]=b[i];
if(S==T)K++;
node tmp;tmp.v=S,tmp.f=h[S],q.push(tmp);
for(;!q.empty();){
int x=q.top().v,y=q.top().f;q.pop();
count[x]++;
if(count[T]==K){fout<<y;return 0;}
if(count[x]>K)continue;
PFOR(p,head[x],next){
tmp.v=to[p];
tmp.f=y-h[x]+w[p]+h[tmp.v];
q.push(tmp);
}
}
//
fin.close();
fout.close();
return 0;
}