分析

因为有 条可以免费，所以我们朴素的最短路算法不太好做。现在题解中有了二分最短路的题解。这里换一种思路。分层图。每一层和原图是相同的，层与层之间由边权为 的边链接。最后一层的终点的权值就是我们要求的最小值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2020,P=10011,INF=0x3f3f3f3f;
struct node
{
    int v,Next,w;
}e[N*P];
int head[N*N],ecnt;
void add(int u,int v,int w)
{
    e[++ecnt].Next=head[u];
    head[u]=ecnt;
    e[ecnt].v=v;
    e[ecnt].w=w;
}
int d[N*N],vis[N*N];
queue<int> q;
int n,p,k;
void spfa()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;vis[1]=1;
    q.push(1);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].Next)
        {
            int to=e[i].v;
            int w=e[i].w;
            if(d[to]>max(d[u],w))
            {
                d[to]=max(d[u],w);
                if(!vis[to])
                {
                    q.push(to);
                    vis[to]=1;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>p>>k;
    for(int i=1;i<=p;++i)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        for(int j=0;j<=k;++j)
        {
            add(x+j*n,y+j*n,z);
            add(y+j*n,x+j*n,z);
        }
        for(int j=0;j<k;++j)
        {
            add(x+j*n,y+(j+1)*n,0);
            add(y+j*n,x+(j+1)*n,0);
        }
    }
    spfa();
    if(d[(k+1)*n]==INF) cout<<-1;
    else cout<<d[(k+1)*n];
    return 0;
}