洛谷 P2966 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-23 19:20:03

发布于：北京

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 个点和 $m$ 条边，每个点有个过路费，每条边有边权
允许：
从起点走到终点，求最小代价
代价为：起点走到终点的边权+经过所有点的过路费最大值
限制：

1.3 题目数据范围与猜测

$1 \le n \le 250$

1.4 一句话概括题意

有 $n$ 个节点， $m$ 条边，求最短路（定义为起点走到终点的边权+经过所有点的过路费最大值）

2 题目破题推导

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词： $1 \le n \le 250$ ，全源最短路 $\longrightarrow$ $\huge{floyd}$

最短路好求，那么过路费最大值怎么办呢？
这时候可以用贪心+递推
就是排序点权（因为floyd不受松弛点顺序的影响），然后对于排完序后的点权求最短路，而已经排好序了，所以只需要找到 $c_i,c_j,c_k$ 中的最大值
那么有两个问题：
第一个：为什么可以是 max ({c [i].v, c [k].v, c [j].v}) 三个点中取最大，凭什么保证这三个点中必出一个最大的过路费
因为大部分时候这个 max 算出来的数字偏大，只有刚好轮到放开路径最大点那一轮，算出来的数字才等于真实值。
第二个：为什么有可能在 dis 松弛的时候并没有通过中转点 k，还是可以含上 c [k].v 去计算？
因为Floyd 的 k 只是 “允许使用的中转集合扩容标记”，不代表路径必须经过c[k]，因此不会破坏答案正确性，只是多做了一点无效计算。

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}

int n, m, q;
const int N = 255;
struct node{
    int idx;
    int v;
}c[N];
bool cmp(node x, node y){
    return x.v < y.v;
}
int dis[N][N], ans[N][N];
const int INF = 0x3f3f3f3f3f3f3f3f;

signed main(){

    n = read(), m = read(), q = read();
    for (int i = 1;i <= n;i++){
        c[i].v = read();
        c[i].idx = i;
    }
    sort(c + 1, c + 1 + n, cmp);
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 1;i <= m;i++){
        int u = read(), v = read(), w = read();
        dis[u][v] = min(dis[u][v], w);
        dis[v][u] = min(dis[v][u], w);
    }
    for (int k = 1;k <= n;k++){
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= n;j++){
                dis[c[i].idx][c[j].idx] = min(dis[c[i].idx][c[j].idx], dis[c[i].idx][c[k].idx] + dis[c[k].idx][c[j].idx]);
                ans[c[i].idx][c[j].idx] = min(ans[c[i].idx][c[j].idx], dis[c[i].idx][c[j].idx] + max({c[i].v, c[k].v, c[j].v}));
            }
        }
    }
    while(q--){
        int si = read(), ti = read();
        cout << ans[si][ti] << endl;
    }
        
    return 0;
}