AcWing 340. 通信线路

题目描述

在郊区有 N 座通信基站,P 条双向电缆,第 i 条电缆连接基站$A_i$和$B_i$。

特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。

现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费$L_i$。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第1行:三个整数N,P,K。

第2..P+1行:第 i+1 行包含三个整数$A_i,B_i,L_i$。

输出格式

包含一个整数表示最少花费。

数据范围

$0 \le K < N \le 1000$,
$1 \le P \le 10000$,
$1 \le L_i \le 1000000$

输入样例:

1
2
3
4
5
6
7
8
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例:

1
4

解题报告

题意理解

就是让你从起点$1$,到终点$N$,找一条代价最少的路径,每一条路径的代价是这条路径上的最大权值,且你可以指定一条路径上$K$条边权值为零.

思路解析

首先我们一眼就可以确定这道题目是的最短路算法.毕竟题目上白纸黑字上写着要,求出最短路.

首先我们一步步分析一下,这道题目的几个关键点.

  1. 这道题目的路径代价是什么?

我们发现,这里的路径不同于一般的最短路,每一条路径的最大边是这条路径的最小值

  1. 题目中有些路径可以清零,这怎么办?

所有关于边的条件或者性质,其实都可以认为是一种特殊边.

这道题目中,有些边可以代价为0,那么我们不妨设置一种特殊边.

比如说$(a,b)$是相连的边,他们代价是$c$,那么如果说我们让它免费,不就是又多了一条边,$(a,b)$,只不过他们的代价是0?

所谓的路径可以免费,就是多了一条为0的重边.

所以这道题目的性质,转换一下就是,我们可以设置K条为权值0的边.


所以我们可以设置一个数组$d[x,p]$表示从1号节点到$x$号节点,途中经过$p$条权值为0的边,

  1. 新加入的边是非0边.

那么我们面对每一条新加入的边$(x,y,z)$我们的$d[y,p]=max(d[x,p],z)$,其中$z$为$(x,y)$权值.

  1. 新加入的边是0边.

如果新加入的边是权值为0的边,显然是$d[y,p+1]=d[x,p]$.


代码解释

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
#include <bits/stdc++.h>
using namespace std;
const int N=10000*3+100;
const int M=1100;
int tot,n,m,k,ver[N],Next[N],head[N],edge[N],dis[M][M];
bool vis[M];
queue<int> q;
void spfa(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[s][0]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for (int i=head[x]; i ; i=Next[i])
{
int j=edge[i],z=ver[i],w=max(dis[x][0],z);
if (dis[j][0]>w)
{
dis[j][0]=w;
if(!vis[j])
q.push(j),vis[j]=1;
}
for(int p=1; p<=k; p++)
{
int w=min(dis[x][p-1],max(dis[x][p],z));
if (dis[j][p]>w)
{
dis[j][p]=w;
if(!vis[j])
q.push(j),vis[j]=1;
}
}
}
}
}
void add(int a,int b,int c)
{
edge[++tot]=b;
ver[tot]=c;
Next[tot]=head[a];
head[a]=tot;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa(1);
int ans=1e9;
for(int i=0; i<=k; i++)
ans=min(ans,dis[n][i]);
if (ans==1e9)
printf("-1");
else
printf("%d",ans);
return 0;
}