洛谷 P3110 分析（别看）

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

2026-07-22 15:16:59

发布于：北京

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有 $n$ 个节点和 $m$ 条无权双向边
允许：
现在有两个人，其中一个人初始在 $1$ 号点，每走一条边需要花费 $B$ 的体力，另一个人初始在 $2$ 号点，每走一条边需要花 $E$ 的体力，如果到某个点这两个人汇合了，那么他们一起走需要花费 $P$ 的体力。
求两人从 $1$ 号点走到 $n$ 号点的最小花费

限制：
可能出现 $P > B+E$ 的情况

1.3 题目数据范围与猜测

$1 \le n \le 4\times10^4 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一些点，求两人通过一些耗费体力的规则从各自的起点走到共同的终点所需最小花费

2 题目破题推导

2.1 化繁为简

我们知道，从各自的起点走到终点的最短路，无非就两种情况：

前面先分开走，走到中间某个点 $x$ 汇合，接着一起走
一直分开走，永不汇合（出现这种情况只有两种可能： $P > B+E$ 或者中间尝试汇合不是最短路）
那么我们可以把这种方案看成：在点 $n$ 汇合，只不过汇合之后没有新的花费了

不论是哪种情况，花费都是：

$所有可能的\\ min(B\times dis[1\rightarrow x]+E\times dis[2\rightarrow x]+P\times dis[x\rightarrow n])\\ 其中dis代表最少边数$

为什么永不汇合的情况也可以这样呢？
因为前面提到过，永不汇合的汇合点就是在点 $n$ ，那这样 $B\times dis[1\rightarrow x]$ 相当于第一个人走到终点， $E\times dis[2\rightarrow x]$ 相当于第二个人走到终点， $P\times dis[x\rightarrow n]=0$ 不影响结果

3 模型匹配

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

关键词：无权图最短边数 $\longrightarrow$ $\huge{bfs}$
bfs即可，最短路较为复杂，因为这题bfs的是最少边数，相当于无权图

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 B, E, P, n, m;
const int N = 4e4 + 10;
vector<int> g[N];
int dis1[N], dis2[N], disn[N];
bool vis[N];
void bfs1(){
    memset(vis, false, sizeof(vis));
    dis1[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0;i < g[u].size();i++){
            int v = g[u][i];
            if (vis[v] == false){
                dis1[v] = dis1[u] + 1;
                vis[v] = true;
                q.push(v);
            }
        }
    }
}
void bfs2(){
    memset(vis, false, sizeof(vis));
    dis2[2] = 0;
    queue<int> q;
    q.push(2);
    vis[2] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0;i < g[u].size();i++){
            int v = g[u][i];
            if (vis[v] == false){
                dis2[v] = dis2[u] + 1;
                vis[v] = true;
                q.push(v);
            }
        }
    }
}
void bfsn(){
    memset(vis, false, sizeof(vis));
    disn[n] = 0;
    queue<int> q;
    q.push(n);
    vis[n] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0;i < g[u].size();i++){
            int v = g[u][i];
            if (vis[v] == false){
                disn[v] = disn[u] + 1;
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

signed main(){

    B = read(), E = read(), P = read(), n = read(), m = read();
    for (int i = 1;i <= m;i++){
        int x, y;
        x = read(), y = read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs1();bfs2();bfsn();
    int mn = LLONG_MAX;
    for (int i = 1;i <= n;i++){
        mn = min(mn, B * dis1[i] + E * dis2[i] + P * disn[i]);
    }
    cout << mn;
    
    return 0;
}