# 340. 通信线路

# 分层图做法

建 k+1 层图,相邻两层图之间权值为 0,代表免费升级,在一层图里面跑就去找最大值,最后的答案就是第 k+1 层的 dis [n] 也就是 dis [(k+1)*n],注意的是这样的做法只有在边数大于 k 时成立,当全部边都可以免费升级时,会出现问题,还没有跑到最后一层图就到达终点了,这时就会往回跑,导致边权增加,就会出错,所以需要把层与层之间的终点连接起来,使它们可以免费互相到达

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int to,next,w;
}e[10000010];
struct Node{
	int u,d;
	bool operator<(const Node &o)const{
		return d>o.d;
	}
};
int head[MAXN];
int dis[MAXN];
int n,p,k,tot;
priority_queue<Node> pq;
void add(int u,int v,int w){
	e[tot]={v,head[u],w};
	head[u]=tot++;
}
void dij(int s){
	memset(dis,0x3f,sizeof dis);
	pq.push({s,0});
	dis[s]=0;
	while(!pq.empty()){
		Node now=pq.top();
		pq.pop();
		for(int i=head[now.u];~i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(dis[v]>max(dis[now.u],w)){
				dis[v]=max(dis[now.u],w);
				pq.push({v,dis[v]});
			}
		}
	}
}
int main(){
	ios;
	memset(head,-1,sizeof head);
	cin>>n>>p>>k;
	while(p--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
		for(int j=1;j<=k;j++){
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
		}
	}
	for(int i=1;i<=k;i++){
		add(i*n,(i+1)*n,0);  // 把终点连成一体 
	}
	dij(1);
	if(dis[(k+1)*n]!=INF)cout<<dis[(k+1)*n]<<'\n';
	else cout<<-1<<'\n'; 
	return 0;
}

# 二分做法

题目求的就是第 k+1 大最小,一看求较大值最小,就要想到二分,二分答案,验证答案,标记大于验证值的边权为 1,小于等于的为 0,求起点到终点的最短路径,路径和小于等于 k 时即满足要求,否则不满足

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int to,next,w;
}e[MAXN];
struct Node{
	int u,d;
	bool operator<(const Node &o)const{
		return d>o.d;
	}
};
int head[MAXN],dis[MAXN];
int n,p,k,tot;
priority_queue<Node> pq;
void add(int u,int v,int w){
	e[tot]={v,head[u],w};
	head[u]=tot++;
}
bool check(int x){
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	pq.push({1,0});
	while(!pq.empty()){
		Node now=pq.top();
		pq.pop();
		for(int i=head[now.u];~i;i=e[i].next){
			int v=e[i].to,w=e[i].w>x?1:0;
			if(dis[v]>dis[now.u]+w){
				dis[v]=dis[now.u]+w;
				pq.push({v,dis[v]});
			}
		}
	}
	if(dis[n]<=k) return 1;
	return 0;
}
int main(){
	ios;
	memset(head,-1,sizeof head);
	cin>>n>>p>>k;
	while(p--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	int l=0,r=1000000,ans=INF,mid;
	while(r>=l){
		mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1; 
	}
	if(ans!=INF) cout<<ans<<'\n';
	else cout<<-1<<'\n';
	return 0;
}

# 动态规划做法

从起点到终点的一条路径中最多有 k 条免费升级,那给 dis 数组多加一维表示从起点到这个点已经免费升级几条边了,数组值依旧表示这个状态需要升级的最大值

转移方程:

若在这条边不使用机会:dis [y, p] = min (dis [y, p], max (dis [x, p], w))
若在这条边使用机会:dis [y, p+1] = min (dis [y, p+1], dis [x, p])

题解中很多都用 SPFA,但这道题目都是正权,dijistla 就可以,省了常数的时间,更新 dis 数组时变成转移方程就可以了

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int to,next,w;
}e[MAXN];
struct Node{
	int u,c;
};
int head[MAXN],dis[1100][1010];
int n,m,tot,k;
queue<Node> pq;
void add(int u,int v,int w){
	e[tot]={v,head[u],w};
	head[u]=tot++;
}
int dij(int s){
	memset(dis,0x3f,sizeof dis);
	pq.push({s,0});
	dis[s][0]=0;
	while(!pq.empty()){
		Node now=pq.front();
		pq.pop();
		for(int i=head[now.u];~i;i=e[i].next){
			int v=e[i].to,w=e[i].w;
			if(dis[v][now.c]>max(dis[now.u][now.c],w)){
				dis[v][now.c]=max(dis[now.u][now.c],w);
				pq.push({v,now.c});
			}
			if(now.c+1<=k && dis[v][now.c+1]>dis[now.u][now.c]){
				dis[v][now.c+1]=dis[now.u][now.c];
				pq.push({v,now.c+1});
			}
		}
	}
	return 1;
}
int main(){
	ios;
	memset(head,-1,sizeof head);
	cin>>n>>m>>k;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dij(1);
	int ans=INF;
	for(int i=0;i<=k;i++){
		ans=min(ans,dis[n][i]);
	}
	if(ans!=INF)cout<<ans<<'\n';
	else cout<<-1<<'\n';
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝