洛谷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;
}