340. 通信线路
分层图做法
建k+1层图，相邻两层图之间权值为0，代表免费升级，在一层图里面跑就去找最大值，最后的答案就是第k+1层的dis[n]也就是dis[(k+1)*n]，注意的是这样的做法只有在边数大于k时成立，当全部边都可以免费升级时，会出现问题，还没有跑到最后一层图就到达终点了，这时就会往回跑，导致边权增加，就会出错，所以需要把层与层之间的终点连接起来，使它们可以免费互相到达
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #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时即满足要求，否则不满足
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #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数组时变成转移方程就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #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;
}
|
wechat
alipay