Luogu p2939 [usaco09feb]revamping trails G

Luogu P2939 [USACO09FEB]Revamping Trails G Answer key

Topic link ：P2939 [USACO09FEB]Revamping Trails G

The question ：

John has a total of $N$ A ranch . from $M$ A dusty path connects . The path allows two-way traffic . Every morning John comes from the pasture $1$ Set off for the pasture $N$ Go and examine the cow .

It takes time to cross each trail . John is going to upgrade $K$ A path , Make it a highway . The traffic on the highway is almost instantaneous , Therefore, the traffic time of expressway is $0$.

Please help John decide which paths to upgrade , Make him from $1$ Ranch No. to No $N$ It takes the shortest time to pasture No .

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

Consider building a layered graph to run the shortest path

First build $k+1$ The same graph

The first $i$ The node of the layer $u_i$ towards The first $i+1$ Layer of $v_i$ Even the edge

Indicates that it has been used $i$ Time modification , Now it's number one $i+1$ Time modification , The change is $(u,v)$ This side

Then run a single source shortest circuit

Note that arrays with edges are usually opened $M\times (K+1)\times 4$

Then there may be a time when you can't get there $k$ The situation where the edge is reached

So put every $in$ and $(i+1)n$ Even the edge

The final answer is $d_{kn+n}$

Be careful $d$ The array should be opened long long

Time complexity $O(kn\log km)$

Code ：

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

Reprint please explain the source