(SPFA最短路)

用d[x][p]表示从1号节点到达x号节点,途中已经指定了p条免费电缆时,经过的路上最贵的电缆花费最小是多少.

如果d[y][p]从d[x][p]转移过来,那么从基站x到基站y的最小花费为到基站x的最小花费与从x到y的花费的两者中的最大值(max(d[x][j],z)).

如果d[y][p]从d[x][p-1]转移过来,由于多了一条免费的电缆,所以这是一条长度为0的边.

d[y][p]要么从d[x][p]转移过来要么从d[x][p-1]转移过来,所以最小的花费为min(d[x][j-1],max(d[x][j],z).

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;
const int M = 20005;
const int INF = 1e9;

int tot,n,p,k;
int ver[M], Next[M], head[M], edge[M];
int d[N][N];
bool v[N];

queue<int> q;

void spfa()
{
    memset(d,0x3f,sizeof(d));

    d[1][0] = 0;
    v[1] = 1;
    q.push(1);

    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        v[x] = 0;

        for (int i = head[x]; i ; i = Next[i])
        {
            int y = ver[i],z = edge[i];
            if (d[y][0] > max(d[x][0],z))
            {
                d[y][0] = max(d[x][0],z);
                if(!v[y]) q.push(y),v[y] = 1;
            }

            for (int j = 1; j <= k; ++ j )
            {
                if (d[y][j] > min(d[x][j-1],max(d[x][j],z)))
                {
                    d[y][j] = min(d[x][j-1],max(d[x][j],z));
                    if(!v[y]) q.push(y),v[y] = 1;
                }
            }
        }
    }
}

void add(int x,int y,int z)
{
    ver[++tot] = y,Next[tot] = head[x], edge[tot] = z, head[x] = tot;
}

int main()
{
    scanf("%d %d %d",&n,&p,&k);

    for (int i = 1; i <= p; ++ i )
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }

    spfa();

    int ans = INF;
    for (int i = 0; i <= k; ++ i ) ans = min(ans,d[n][i]);

    if (ans == INF) printf("%d\n",-1);
    else printf("%d\n",ans);

    return 0;
}