P4568 [JLOI2011] 飞行路线 题解

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,s,t,f[100001][21];
struct edge{
	ll nt,to,vl;
}p[1000001];
ll hd[1000001],nm;
void ad(ll x,ll y,ll z){
	p[++nm].nt=hd[x];
	p[nm].to=y;
	p[nm].vl=z;
	hd[x]=nm;
}
//建图ing
struct vs{
	ll x,vl;
	vs(ll a,ll b){
		x=a;
		vl=b;
	}
	bool operator <(const vs b) const{
        return vl>b.vl;
    }
};
//dfs ing
priority_queue<vs> q;
void djstl(){
	for(ll i=0;i<=k;i++)
		f[s][i]=0;
	for(ll i=0;i<=k;i++){
		q.push(vs(s,0));
		while(!q.empty()){
			vs u=q.top();
			q.pop();
			if(u.vl>f[u.x][i]) continue;
			for(ll j=hd[u.x];j;j=p[j].nt){
				ll v=p[j].to;
				bool bl=0;
				if(i)
					if(f[v][i]>f[u.x][i-1]){
						f[v][i]=f[u.x][i-1];
						bl=1;
					}
				if(f[v][i]>f[u.x][i]+p[j].vl){
					f[v][i]=f[u.x][i]+p[j].vl;
					bl=1;
				}
				if(bl) q.push(vs(v,f[v][i]));
			}
		}
	}
}
//DPing
int main(){
	cin>>n>>m>>k>>s>>t;
	for(ll i=1;i<=m;i++){
		ll x,y,z;
		cin>>x>>y>>z;
		ad(x,y,z);
		ad(y,x,z);
	}
	for(ll i=0;i<n;i++)
		for(ll j=0;j<=k;j++)
			f[i][j]=1e9;
	djstl();
	cout<<f[t][k];
	return 0;
}
//没了