提交了N次啊，最后發(fā)現(xiàn)是沒有處理最后無解輸出-1的情況（只有少于K條路徑）。
逐一搜索第1短、第2短、第3短。。。的路徑，count統(tǒng)計一個點(diǎn)入隊(duì)的次數(shù)。
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]])//這里不是標(biāo)準(zhǔn)的SPFA，對于A*的H，可以近似的處理？？
//完了，我又不確定了。。。 標(biāo)準(zhǔn)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;
}