题意

有任意k条边可以免费的dijkstra。

思路

都说了是dijkstra就跑dijkstra先，跑完再说。

跑完之后发现有个免费的问题需要处理。

那就给dijkstra数组加上一维。

f[i][j]表示从s出发，免了j条边的费到i的最少费用。

每次dijkstra的时候循环一遍，处理f[u][所有j]。如果有需要push就做标记最后再push。

最后输出f[t]的最小值即可。

自己钻研出来的野路子，可能不是最优解，有望指正。

代码

#include<iostream>
#include<vector>
#include<queue>
#define N 20000
#define K 20
#define inf 2147483647
#define halfinf 1073741823
using namespace std;
struct edge{
	int v,w;
};
vector<edge>a[N];
int f[N][K];
int n,m,k,s,t;
int main();
void build();
void dijkstra();
void init();
int main(){
	build();
	dijkstra();
	int ans=inf;
	for(int i=0;i<=k;i++)
		ans=min(ans,f[t][i]);//输出f[t]的最小 
	cout<<ans;
	return 0;
}
void build(){
	cin>>n>>m>>k>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back({v,w});
		a[v].push_back({u,w});
	}
}
void dijkstra(){
	init();
	f[s][0]=0;
	priority_queue<pair<int,int>>p;
	p.push({0,s});
	while(!p.empty()){
		int u=p.top().second;
		p.pop();
		for(auto i:a[u]){
			int v=i.v,w=i.w,s=inf;
			bool push=false;
			for(int j=0;j<=k;j++){//循环每一个j 
				if(f[v][j]>f[u][j]+w){//不免费 
					f[v][j]=f[u][j]+w;
					push=true;
					s=min(s,f[v][j]);
				}
				if(j+1<=k&&f[v][j+1]>f[u][j]){//免费 
					f[v][j+1]=f[u][j];
					push=true; 
					s=min(s,f[v][j+1]);
				}
			}
			if(push)//统一push 
				p.push({-s,v});
		}
	}
}
void init(){
	for(int i=0;i<N;i++)
		for(int j=0;j<K;j++)
			f[i][j]=halfinf;
}

给我点差评

#include<bits/stdc++.h>
using namespace std;
const int K=13,N=1e4+2;
int n,m,k,s,t;
struct edge
{
	int d,v,w;
};
vector<edge>g[K][N];
bool vis[K][N];
int dis[K][N];
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;

void dijkstra()
{
	memset(dis,0x3f,sizeof dis);
	dis[1][s]=0;
	q.push({0,{1,s}});
	while(!q.empty())
	{
		int d=q.top().second.first,u=q.top().second.second;
		q.pop();
		if(vis[d][u])continue;
		vis[d][u]=1;
		for(auto v_:g[d][u])
		{
			int vd=v_.d,v=v_.v,w=v_.w;
			if(dis[d][u]+w<dis[vd][v])
			{
				dis[vd][v]=dis[d][u]+w;
				q.push({dis[vd][v],{vd,v}});
			}
		}
	}
}
signed main()
{
	cin>>n>>m>>k>>s>>t;
	for(int i=1,a,b,c;i<=m;i++)
	{
		cin>>a>>b>>c;
		for(int j=1;j<=k+1;j++)
		{
			g[j][a].push_back({j,b,c});
			g[j][b].push_back({j,a,c});
		}
	}
	for(int i=1;i<=k+1;i++)
		for(int j=0;j<n;j++)
			for(auto v:g[i][j])
				g[i][j].push_back({i+1,v.v,0});
	dijkstra();
	int mi=2e9;
	for(int i=1;i<=k+1;i++)
		mi=min(mi,dis[i][t]);
	cout<<mi;
	return 0;
}

分层写法

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+5;
const int MAXK=11;
struct Edge{
	int to,cost;
};
struct Node{
	int u,k;
	long long dist;
	bool operator>(const Node& other)const{return dist>other.dist;}
};
vector<Edge>graph[MAXN];
long long dist[MAXN][MAXK];
bool vis[MAXN][MAXK];
int main() {
	int n,m,k,s,t;
	cin>>n>>m>>k>>s>>t;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		graph[a].push_back({b,c});
		graph[b].push_back({a,c});
	}
	memset(dist,0x3f,sizeof dist);
	memset(vis,false,sizeof vis);
	priority_queue<Node,vector<Node>,greater<Node>>pq;
	dist[s][0]=0;
	pq.push({s,0,0});
	while(!pq.empty()){
		Node now=pq.top();
		pq.pop();
		int u=now.u;
		int cnt=now.k;
		long long d=now.dist;
		if (vis[u][cnt])continue;
		vis[u][cnt]=true;
		for(int i=0;i<graph[u].size();i++){
			int v=graph[u][i].to;
			int w=graph[u][i].cost;
			if(!vis[v][cnt]&&dist[v][cnt]>d+w)//不免费 
				dist[v][cnt]=d+w,
				pq.push({v,cnt,dist[v][cnt]});
			if(cnt<k&&!vis[v][cnt+1]&&dist[v][cnt+1]>d)//免费 
				dist[v][cnt+1]=d,
				pq.push({v,cnt+1,dist[v][cnt+1]});
		}
	}
	long long ans=1e18;
	for(int i=0;i<=k;i++)
		ans=min(ans,dist[t][i]);
	cout<<ans;
	return 0;
}