洛谷P2939 [USACO09FEB]Revamping Trails G 题解

题目链接：P2939 [USACO09FEB]Revamping Trails G

题意：

约翰一共有 $N$ 个牧场.由 $M$ 条布满尘埃的小径连接。小径可以双向通行。每天早上约翰从牧场 $1$ 出发到牧场 $N$ 去给奶牛检查身体。

通过每条小径都需要消耗一定的时间。约翰打算升级其中 $K$ 条小径，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 $0$。

请帮助约翰决定对哪些小径进行升级，使他每天从 $1$ 号牧场到第 $N$ 号牧场所花的时间最短。

$1\le n\le 10^4,1\le m\le 5\times 10^4,1\le k\le 20$

考虑建分层图跑最短路

首先建 $k+1$ 个同样的图

第 $i$ 层的结点 $u_i$ 向 第 $i+1$ 层的 $v_i$ 连边

表示已经用了 $i$ 次修改，现在是第 $i+1$ 次修改，修改的是 $(u,v)$ 这条边

然后跑一个单源最短路就好了

注意存边的数组一般要开 $M\times (K+1)\times 4$

然后有点时候可能会出现走了不到 $k$ 条边就到了的情况

所以要把每个 $in$ 和 $(i+1)n$ 连边

最后答案就是 $d_{kn+n}$

注意 $d$ 数组应该要开long long

时间复杂度 $O(kn\log km)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
// #define int long long
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e4+5)
#define K (int)(22)
#define M (int)(5e4+5)
struct Edge{int u,v,w,next;}e[M*K*4];
struct node{int u; ll dis;};
ll d[N*K];
bool operator<(node a,node b){return a.dis>b.dis;}
int n,m,k,pos=1,head[N*K],vis[N*K];
priority_queue<node> q;
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dijkstra(int st)
{
    memset(d,0x3f,sizeof(d));
    d[st]=0; q.push({st,0});
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v,w=e[i].w;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> k;
    for(int i=1,u,v,w; i<=m; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);addEdge(v,u,w);
        for(int j=1; j<=k; j++)
        {
            addEdge(j*n+u,j*n+v,w);
            addEdge(j*n+v,j*n+u,w);
            addEdge((j-1)*n+u,j*n+v,0);
            addEdge((j-1)*n+v,j*n+u,0);
        }
    }
    for(int i=1; i<=k; i++)
        addEdge((i-1)*n+n,i*n+n,0);
    dijkstra(1);
    cout << d[k*n+n] << '\n';
    return 0;
}
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
72
73

转载请说明出处