题意简述

一条路径的权值为这条路径的最大的边的权值，可以屏蔽K条边， 求起点(1)到终点(n)的最短路。

分析

考虑 K = 0时， 可以Dij最短路， 且可以保证正确性。（最先弹出的结果是最优结果，较差的结果即使入堆也不会弹出）

考虑 K != 0时， 依然可以最短路， 只是节点要记录已屏蔽边的次数。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int maxp = 10005;

int N, P, K;
int ct, hed[maxp << 1], nxt[maxp << 1], ver[maxp << 1], val[maxp << 1];
void ad(int a, int b, int c)
{
    ver[++ct] = b;
    val[ct] = c;
    nxt[ct] = hed[a];
    hed[a] = ct;
}

//
int dis[maxn][maxn];
bool vis[maxn][maxn];
struct heapnode
{
    int u, d, used;
};
bool operator<(heapnode a, heapnode b)
{
    return !(a.d < b.d);
}

void Dij()
{
    priority_queue<heapnode> Q;
    memset(dis, 63, sizeof dis);
    dis[1][0] = 0;
    Q.push( (heapnode){1, 0, 0} );
    while(!Q.empty())
    {
        heapnode node = Q.top(); Q.pop();
        int x = node.u;
        int k = node.used;
        if(vis[x][k]) continue; else vis[x][k] = 1;
        for(int i=hed[x]; i; i=nxt[i])
        {
            int y = ver[i], z = val[i];
            if( dis[y][k] > max(dis[x][k], z))
            {
                dis[y][k] = max(dis[x][k], z);
                Q.push((heapnode){y,dis[y][k],k});
            }
            if(k<K && dis[y][k+1]>dis[x][k])
            {
                dis[y][k+1] = dis[x][k];
                Q.push((heapnode){y,dis[y][k+1],k+1});
            }
        }
    }
    for(int i=1;i<=K;++i) dis[N][i] = min(dis[N][i], dis[N][i-1]);
    if(dis[N][K] != 1061109567) cout << dis[N][K];
    else cout << -1;
}

int main()
{

    scanf("%d%d%d", &N, &P, &K);
    for(int i=0; i<P; ++i)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        ad(a,b,c), ad(b,a,c);
    }
    //init

    Dij();

    return 0;

}