# 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; | |
} |
