首页 程序设计 图与树 最短路算法

# 洛谷仙题

# 题目大意

给定一个有 nn 个节点，mm 条边的无向图。求节点 xx 到节点 yy 的最小权值

# 数据范围

  • 1≤n≤106,1≤m≤106×1.51 \le n \le 10^6,1 \le m \le 10^6 \times 1.5
  • 1≤ci≤10001 \le c_i \le 1000

# 题解

这题会卡 vector<PII> g[M] 的存图，得用 链式前向星

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int N = 1e6 + 10, M = 3e6 + 10;

vector<int> d;
vector<bool> st;

int n, m, s, t;
int h[M], e[M], ne[M], w[M], idx = 0;

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

void solve() {
    cin >> n >> m >> s >> t;
    st = vector<bool>(n + 1), d = vector<int>(n + 1, 0x3f3f3f3f);
    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    d[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    heap.push({0, s});

    while (!heap.empty()) {
        int u = heap.top().second;
        heap.pop();
    
        if (st[u])
            continue;

        st[u] = true;

        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i], val = w[i];

            if (d[v] > d[u] + val)
                d[v] = d[u] + val, heap.push({d[v], v});
        }
    }
    
    cout << d[t] << endl;
}

# 2024 睿抗 - D 题

# 题目大意

现在有 nn 个城市，mm 条道路

  • 每个城市有一个热度值
  • 每条道路有一个花销
    现在我要从 ss 城市到 tt 城市，请你求出最小花销的路线，如果有多条最小花销路线，则取途径城市最高热度值最小的那一条路线，请你计算这样的路线的最小花销和途径城市的最高热度值

# 数据范围

  • 1≤n≤1031 \le n \le 10^3
  • 1≤m≤5n1 \le m \le 5n

# 题解

这个题目优先要保证的是路线花销最小，在路线花销最小的基础上，选取途径城市最高热度值最小的那条
所以我们可以在堆优化的 DijkstraDijkstra 找最短路的基础上，添加上维护热度值的 maxVal 数组的语句

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (auto [v, val] : g[u]) {
    if (d[v] < d[u] + val)
        continue;

    // 有路径更短的，肯定会更新
    if (d[v] > d[u] + val)
        d[v] = d[u] + val, heap.push({d[v], v});

    if (v != t)
        // min 表示，最大的里面选最小的
        // max 表示，在路径中选最大 hot 值的城市
        maxVal[v] = min(maxVal[v], max(maxVal[u], hot[v]));
    else
        maxVal[v] = maxVal[u];
}

重点在 maxVal[v] = min(maxVal[v], max(maxVal[u], hot[v])) ，要理解清楚

  • maxmax 是用来满足：选取途径城市最高热度值最小的那条
  • minmin 是用来满足：选取途径城市最高热度值最小的那条
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    int n, m, s, t;
    vector<int> hot, d, maxVal;
    vector<PII> g[N];
    vector<bool> st;

    void solve () {
        cin >> n >> m >> s >> t;
        hot = vector<int>(n + 1), d = vector<int>(n + 1, 1e18), st = vector<bool>(n + 1);
        maxVal = vector<int>(n + 1, 1e18);

        for (int i = 1; i <= n; i++)
            cin >> hot[i];

        for (int i = 1, u, v, val; i <= m; i++) {
            cin >> u >> v >> val;
            g[u].push_back({v, val}), g[v].push_back({u, val});
        }

        // 先满足路径值最小，如果有更小的，那我要找热力值最小的

        // Tul [point, val, maxVal]：点，边权值，最大热度
        priority_queue<PII, vector<PII>, greater<PII>> heap;
        maxVal[s] = 0, d[s] = 0, heap.push({d[s], s});

        while (heap.size()) {
            int u = heap.top().second;
            heap.pop();

            if (st[u])
                continue;

            st[u] = 1;

            for (auto [v, val] : g[u]) {
                if (d[v] < d[u] + val)
                    continue;

                // 有路径更短的，肯定会更新
                if (d[v] > d[u] + val)
                    d[v] = d[u] + val, heap.push({d[v], v});

                if (v != t)
                    // min 表示，最大的里面选最小的
                    // max 表示，在路径中选最大 hot 值的城市
                    maxVal[v] = min(maxVal[v], max(maxVal[u], hot[v]));
                else
                    maxVal[v] = maxVal[u];
            }
        }

        if (d[t] == 1e18) {
            cout << "Impossible\n";
            return;
        }

        cout << d[t] << ' ' << maxVal[t] << '\n';
    }

# 2025 睿抗 - D 题

# 题目大意

有 nn 个城市 mm 条路，每个城市有一个停留费用，每条路有一个耗费时间
现在你从 ss 市出发要去 tt 市，请你找到一条，使得途径城市的最贵的停留费用尽可能小的路径，若路径不唯一，则选择总耗费时间最小的那个

# 数据范围

  • 1≤N≤10001 \le N \le 1000
  • 1≤M≤3×1041 \le M \le 3 \times 10^4

# 题解

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
typedef pair<int, int> PII;
typedef array<int, 3> Tul;

const int N = 1e3 + 10;

int n, m, s, t;
vector<int> c, maxVal, d;
vector<PII> g[N];
vector<bool> st;

// Tul : [cost, dist, point]
struct Compare {
    bool operator()(const Tul& x, const Tul& y) {
        if (x[0] != y[0])
            return x[0] > y[0]; // 优先保证点权
        return x[1] > y[1]; // 最大点权最小值相同时，找时间最小
    }
};

void solve () {
    cin >> n >> m;
    c = vector<int>(n + 1), st = vector<bool>(n + 1);
    d = vector<int>(n + 1, 1e18), maxVal = vector<int>(n + 1, 1e18);
    
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w}), g[v].push_back({u, w});
    }

    cin >> s >> t;

    priority_queue<Tul, vector<Tul>, Compare> heap;
    d[s] = 0, maxVal[s] = c[s], heap.push({maxVal[s], d[s], s});

    while (heap.size()) {
        auto [cost, dist, u] = heap.top();
        heap.pop();

        if (dist != d[u] && cost != maxVal[u])
            continue;

        for (auto [v, w] : g[u]) {
            int nMax = max(cost, c[v]), nDis = dist + w;
            
            if (nMax > maxVal[v] || (nMax == maxVal[v] && nDis >= d[v]))
                continue;

            d[v] = nDis, maxVal[v] = nMax, heap.push({nMax, nDis, v});
        }
    }

    if (d[t] == 1e18)
        cout << -1 << ' ' << -1 << '\n';
    else
        cout << maxVal[t] << ' ' << d[t] << '\n';
}