#include<iostream>
#include<algorithm>
#include<queue>
#define inf 2148473647
using namespace std;
struct edge{int to,w,nxt;edge(){};edge(int to,int w,int nxt){this->to=to,this->w=w,this->nxt=nxt;}}edge1[200005],edge2[200005];
int n,m,tot,head1[1005],head2[1005],dis[1005],v[1005],s,t,k;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> >q;
struct node{
	int id,f,g;
	node(){};
	node(int id,int f,int g){
		this->id=id,this->f=f,this->g=g;
	}
	bool operator < (const node &x) const{
		if(f==x.f)return g>x.g;
		return f>x.f;
	}
};
priority_queue<node>qq;
void dijkstra(int s){
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[s]=0;
	q.push(make_pair(dis[s],s));
	int tmp,nxt;
	while(q.size()){
		tmp=q.top().second;q.pop();
		if(v[tmp])continue;
		v[tmp]=1;
		for(int i=head2[tmp];i;i=edge2[i].nxt){
			nxt=edge2[i].to;
			if(dis[nxt]>dis[tmp]+edge2[i].w)dis[nxt]=dis[tmp]+edge2[i].w,q.push(make_pair(dis[nxt],nxt));
		}
	}
}
void a(){
	k+=(s==t);
	qq.push(node(s,0,0));
	node tmp;int to;
	while(qq.size()){
		tmp=qq.top(); qq.pop();
		if(tmp.id==t)
			if(!(--k)){
				printf("%d\n",tmp.g);return;
			}
		for(int i=head1[tmp.id];i;i=edge1[i].nxt){
			to=edge1[i].to;
			qq.push((node){to,tmp.g+edge1[i].w+dis[to],tmp.g+edge1[i].w});
		}
	}
	cout<<-1<<endl;
}

int main()
{
	int u,v,w;
	scanf("%d%d",&n,&m);
	while(m--)scanf("%d%d%d",&u,&v,&w),tot++,edge1[tot]=edge(v,w,head1[u]),head1[u]=tot,edge2[tot]=edge(u,w,head2[v]),head2[v]=tot;
	scanf("%d%d%d",&s,&t,&k);
	dijkstra(t+1);
	a();
}

K短路模板，但是1000点10000边的大数据炸了。

硬是看不出什么问题。dijk和A*都没什么毛病

求助