SPFA + 动态规划

$O(tNP)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1010, M = 20010;

int h[N], to[M], w[M], ne[M], idx;
int d[N][N];
bool vis[N];
//状态表示: d[x, p]表示从1号节点到达基站x，途中已经指定了p条电缆免费时，经过的路径上最贵的电缆的花费最小是多少
//状态计算: 
//不升级当前边: d[y, p] = max(d[x, p], z);
//升级当前边: d[y, p] = min(d[y, p], d[x, p - 1]);


int n, p, k;

void add(int a, int b, int c){
    to[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

void spfa(){
    memset(d, 0x3f, sizeof(d));
    queue<int> q;
    q.push(1);
    d[1][0] = 0;
    vis[1] = true;

    // 将松弛操作更改为状态转移方程，知道不能转移为止
    while(q.size()){
        int x = q.front(); q.pop();
        vis[x] = false;

        for(int i = h[x]; i; i = ne[i]){
            int y = to[i], z = w[i];

            for(int p = 0; p <= k; p++){
                if(d[y][p] > max(d[x][p], z)){  //不升级当前边
                    d[y][p] = max(d[x][p], z);
                    if(!vis[y]){
                        q.push(y);
                        vis[y] = true;
                        }
                    }
                if(p > 0 && d[y][p] > d[x][p - 1]){ //升级当前边
                    d[y][p] = d[x][p - 1];
                    if(!vis[y]){
                        q.push(y);
                        vis[y] = true;
                        }
                    }
                }
            }
        }
}

int main(){
    scanf("%d %d %d", &n, &p, &k);
    int x, y, z;
    while(p--){
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z), add(y, x, z);
        }
    spfa();
    int ans = 0x3f3f3f3f;
    for(int p = 0; p <= k; p++) ans = min(ans, d[n][p]);
    if(ans == 0x3f3f3f3f) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

二分答案 + 双端队列BFS

$O((N + P)log MAX_L)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 1010, M = 20010;

int h[N], to[M], ne[M], w[M], idx;
int dist[N];
bool st[N];
int n, p, k;

void add(int a, int b, int c){
    to[++idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

// 把升级价格大于price的电缆看做长度为1的边，判断到终点是否长度小于等于k即可
bool bfs(int price){
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    deque<int> q;
    q.push_back(1);
    dist[1] = 0;

    while(q.size()){
        int v = q.front(); q.pop_front();
        if(st[v]) continue;
        st[v] = true;
        for(int i = h[v]; i; i = ne[i]){
            int d = 0;
            if(w[i] > price) d = 1;
            if(!st[to[i]] && dist[to[i]] > dist[v] + d){
                dist[to[i]] = dist[v] + d;
                if(d) q.push_back(to[i]);
                else q.push_front(to[i]);
                }
            }
        }

    return dist[n] <= k;
}

int main(){
    scanf("%d %d %d", &n, &p, &k);
    int x, y, z;
    for(int i = 0; i < p; i++){
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
        }
    // 二分答案：支付的钱更多时,合法的升级方案一定包含了花费更少的升级方案
    int l = 0, r = 1e6 + 5;
    while(l < r){
        int mid = l + r >> 1;
        if(bfs(mid)) r = mid;
        else l = mid + 1;
        }

    if(l > 1e6) puts("-1");
    else printf("%d\n", l);
    return 0;
}