luogu P4568 [JLOI2011]飞行路线 最短路Dijkstra+dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=111111;
int f[N][21];
int e[N],ne[N],h[N],idx,w[N];
int n,m,s,t,k;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
struct node{
	int x,vl;
	bool operator < (const node b) const
	{
		return vl>b.vl;
	}
};
priority_queue<node>q;
void djst()
{
	for(int i=0;i<=k;i++)
		f[s][i]=0;
	for(int i=0;i<=k;i++)
	{
		q.push({s,0});
		while(q.size())
		{
			node u=q.top();
			q.pop();
			if(u.vl>f[u.x][i])
				continue;
			for(int j=h[u.x];j!=-1;j=ne[j])
			{
				int v=e[j];
				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]+w[j])
				{
					f[v][i]=f[u.x][i]+w[j];
					bl=1;
				}
				//更新过 
				if(bl)
					q.push({v,f[v][i]});
			}
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>k>>s>>t;
	for(int i=1; i<=m; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<=k;j++)
			f[i][j]=1e9;
	djst();
	cout<<f[t][k]<<endl;
	return 0;
}

luogu P4568 [JLOI2011]飞行路线 最短路Dijkstra+dp

原文：https://www.cnblogs.com/QingyuYYYYY/p/12890916.html