洛谷2939 [USACO09FEB]Revamping Trails

双倍经验：洛谷4568，只需要改数据范围。

题意

有一个 $n(n\le 10000)$ 点 $m(m\le 50000)$ 边的无向图，可以将其中 $k(k\le 20)$ 条边的边权改成 $0$ ，求 $1\rightarrow n$ 的最短路。

题解

分层图最短路。

将图分为 $k+1$ 层，同一层按给出的边连边；第 $i$ 层与第 $i+1$ 层之间也按给出的边连，但权值为 $0$ 。这样走到下一层就相当于将一条边改为 $0$ ，答案就是第一层的 $1$ 到最后一层的 $n$ 的距离。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[4200005];
const int N=210005;
bool vis[N];
int cnt,head[N],n,m,k,a,b,c,dis[N];

inline int f(int x,int y) { return (y-1)*n+x; } //x 在第 y 层的编号

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline int dijkstra()
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue <pii,vector<pii>,greater<pii> > q;
    q.push(mp(0,1));
    while (!q.empty())
    {
        int x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (dis[x]+w<dis[y])
            {
                dis[y]=dis[x]+w;
                q.push(mp(dis[y],y));
            }
        }
    }
    return dis[f(n,k)];
}

signed main()
{
    n=read(); m=read(); k=read()+1;
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        for (int i=1;i<=k;i++)
        {
            add(f(a,i),f(b,i),c);
            add(f(b,i),f(a,i),c);
            if (i==k) break;
            add(f(a,i),f(b,i+1),0);
            add(f(b,i),f(a,i+1),0);
        }
    }
    return !printf("%d",dijkstra());
}