洛谷 P3106 分析（别看）

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

2026-07-24 20:14:41

发布于：北京

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有 $n$ 个交叉路口和 $m$ 条单向边
请注意此题题目描述，清楚表述了是单向边，而后述双向边是指若存在双向边则双向边的给出方式
允许：
第一个GPS认为 $a_i\rightarrow b_i$ 的边权为 $p_i$
第二个GPS认为 $a_i\rightarrow b_i$ 的边权为 $q_i$
当某个GPS认为当前走的路线不是当前这个点到点 $n$ 的最短路径上的点，就会发出一次抱怨
这里当前这个点到点 $n$ 的最短路径上的点这个点很重要，待会对于最短路有帮助
求最小抱怨次数
限制：

1.3 题目数据范围与猜测

$1 \le m \le n \le 10000 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

有 $n$ 个点 $m$ 条单向边，有两种抱怨源头，求抱怨次数最小值

2 题目破题推导

3 模型匹配

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

这题第一个巧妙的点在于：在图上求最小值，自然就匹配上了最短路算法！
点就是题目中给出的点，边权为当前这个点被 $i$ 个GPS抱怨，然后求 $1\rightarrow n$ 最短路
这题第二个巧妙的点在于：如何在满足当前这个点到点 $n$ 的最短路径上的点的情况下找到究竟被多少个GPS抱怨？
我们可以建 $\huge{反向边！}$ ，因为这样就是终点到其余各点的最短路了。
那全部建反向边就好做了（当然所有最短路也要按反向边来算）

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;
const int N = 11111, M = 55555;
struct node{
    int to;
    int w;
};
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<node> g1[N];
int dis1[N];
void dijkstra1(int s){
    memset(dis1, 0x3f, sizeof(dis1));
    dis1[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int d = q.top().first;
        int u = q.top().second;
        q.pop();
        for (int i = 0;i < g1[u].size();i++){
            node now = g1[u][i];
            int v = now.to;
            int w = now.w;
            if (dis1[v] > dis1[u] + w){
                dis1[v] = dis1[u] + w;
                q.push({dis1[v], v});
            }
        }
    }
}
vector<node> g2[N];
int dis2[N];
void dijkstra2(int s){
    memset(dis2, 0x3f, sizeof(dis2));
    dis2[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int d = q.top().first;
        int u = q.top().second;
        q.pop();
        for (int i = 0;i < g2[u].size();i++){
            node now = g2[u][i];
            int v = now.to;
            int w = now.w;
            if (dis2[v] > dis2[u] + w){
                dis2[v] = dis2[u] + w;
                q.push({dis2[v], v});
            }
        }
    }
}
vector<node> gn[N];
int disn[N];
void dijkstran(int s){
    memset(disn, 0x3f, sizeof(disn));
    disn[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int d = q.top().first;
        int u = q.top().second;
        q.pop();
        for (int i = 0;i < gn[u].size();i++){
            node now = gn[u][i];
            int v = now.to;
            int w = now.w;
            if (disn[v] > disn[u] + w){
                disn[v] = disn[u] + w;
                q.push({disn[v], v});
            }
        }
    }
}
struct edge{
    int from, to;
    int pi, qi;
};
vector<edge> temp;

signed main(){

    n = read(), m = read();
    for (int i = 1;i <= m;i++){
        int from = read(), to = read(), pi = read(), qi = read();
        temp.push_back({from, to, pi, qi});
    }
    for (int i = 0;i < m;i++){
        g1[temp[i].to].push_back({temp[i].from, temp[i].pi});
    }
    dijkstra1(n);
    for (int i = 0;i < m;i++){
        g2[temp[i].to].push_back({temp[i].from, temp[i].qi});
    }
    dijkstra2(n);
    for (int i = 0;i < m;i++){
        int cnt = 0;
        if (dis1[temp[i].from] != dis1[temp[i].to] + temp[i].pi){
            cnt++;
        }
        if (dis2[temp[i].from] != dis2[temp[i].to] + temp[i].qi){
            cnt++;
        }
        gn[temp[i].from].push_back({temp[i].to, cnt});
    } 
    dijkstran(1);
    printf("%lld", disn[n]);
    
    return 0;
}