Dijkstra - Variations and Applications

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes shortest and second shortest distances from s to all nodes in a directed graph with non-negative weights.
5
// Input format:
6
// n m
7
// u v w (m lines, 1-indexed vertices)
8
// s t
9
// Output: second shortest distance from s to t (or -1 if not exists)
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m;
16
    if (!(cin >> n >> m)) return 0;
17
    struct Edge {int to; long long w;};
18
    vector<vector<Edge>> g(n + 1);
19
    for (int i = 0; i < m; ++i) {
20
        int u, v; long long w;
21
        cin >> u >> v >> w;
22
        g[u].push_back({v, w});
23
        // If the graph is undirected, also add: g[v].push_back({u, w});
24
    }
25
    int s, t; cin >> s >> t;
26
27
    const long long INF = (long long)4e18;
28
    vector<long long> d1(n + 1, INF), d2(n + 1, INF);
29
    using PLL = pair<long long,int>;
30
    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
31
32
    d1[s] = 0;
33
    pq.push({0, s});
34
35
    while (!pq.empty()) {
36
        auto [dist, u] = pq.top(); pq.pop();
37
        // Ignore if this distance is already worse than our recorded second-best
38
        if (dist > d2[u]) continue;
39
        for (auto [v, w] : g[u]) {
40
            long long nd = dist + w;
41
            if (nd < d1[v]) {
42
                // Found a new best; old best becomes second best
43
                d2[v] = d1[v];
44
                d1[v] = nd;
45
                pq.push({d1[v], v});
46
                if (d2[v] < INF) pq.push({d2[v], v});
47
            } else if (nd > d1[v] && nd < d2[v]) {
48
                // Found a new second-best distinct distance
49
                d2[v] = nd;
50
                pq.push({d2[v], v});
51
            }
52
        }
53
    }
54
55
    if (d2[t] == INF) cout << -1 << "\n";
56
    else cout << d2[t] << "\n";
57
    return 0;
58
}
59

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Finds K shortest s->t walks (non-negative weights). Outputs K distances in non-decreasing order.
5
// This variant allows revisiting nodes; results are walks, not necessarily simple paths.
6
// Input:
7
// n m k
8
// u v w (m lines, 1-indexed)
9
// s t
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m, K; cin >> n >> m >> K;
16
    struct Edge {int to; long long w;};
17
    vector<vector<Edge>> g(n + 1);
18
    for (int i = 0; i < m; ++i) {
19
        int u, v; long long w; cin >> u >> v >> w;
20
        g[u].push_back({v, w});
21
        // For undirected graphs, also add reverse edges
22
    }
23
    int s, t; cin >> s >> t;
24
25
    using PLL = pair<long long,int>;
26
    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
27
    vector<int> cnt(n + 1, 0); // how many times we've finalized node v
28
29
    pq.push({0, s});
30
    vector<long long> answers;
31
32
    while (!pq.empty() && (int)answers.size() < K) {
33
        auto [d, u] = pq.top(); pq.pop();
34
        if (cnt[u] >= K) continue; // already have K best arrivals to u
35
        cnt[u]++;
36
        if (u == t) {
37
            answers.push_back(d);
38
        }
39
        for (auto e : g[u]) {
40
            pq.push({d + e.w, e.to});
41
        }
42
    }
43
44
    for (size_t i = 0; i < answers.size(); ++i) {
45
        cout << answers[i] << (i + 1 == answers.size() ? '\n' : ' ');
46
    }
47
    // If fewer than K paths exist, fewer numbers will be printed.
48
    return 0;
49
}
50

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes shortest paths from s when all edges have weight 0 or 1.
5
// Input:
6
// n m
7
// u v w  (w must be 0 or 1)
8
// s
9
// Output: distances from s to all vertices (or -1 if unreachable)
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m; cin >> n >> m;
16
    struct Edge {int to; int w;};
17
    vector<vector<Edge>> g(n + 1);
18
    for (int i = 0; i < m; ++i) {
19
        int u, v, w; cin >> u >> v >> w; // w in {0,1}
20
        g[u].push_back({v, w});
21
        // For undirected graphs, also add: g[v].push_back({u, w});
22
    }
23
    int s; cin >> s;
24
25
    const int INF = 1e9;
26
    vector<int> dist(n + 1, INF);
27
    deque<int> dq;
28
    dist[s] = 0;
29
    dq.push_front(s);
30
31
    while (!dq.empty()) {
32
        int u = dq.front(); dq.pop_front();
33
        for (auto [v, w] : g[u]) {
34
            if (dist[v] > dist[u] + w) {
35
                dist[v] = dist[u] + w;
36
                if (w == 0) dq.push_front(v);
37
                else dq.push_back(v);
38
            }
39
        }
40
    }
41
42
    for (int v = 1; v <= n; ++v) {
43
        cout << (dist[v] == INF ? -1 : dist[v]) << (v == n ? '\n' : ' ');
44
    }
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Shortest path from s to t when you may traverse at most one edge for free (cost 0).
5
// Model states as (vertex, usedCoupon in {0,1}). Run Dijkstra on the expanded graph.
6
// Input:
7
// n m
8
// u v w (m lines, w >= 0)
9
// s t
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n, m; cin >> n >> m;
16
    struct Edge {int to; long long w;};
17
    vector<vector<Edge>> g(n + 1);
18
    for (int i = 0; i < m; ++i) {
19
        int u, v; long long w; cin >> u >> v >> w;
20
        g[u].push_back({v, w});
21
        // For undirected graphs, also add reverse edges
22
    }
23
    int s, t; cin >> s >> t;
24
25
    const long long INF = (long long)4e18;
26
    // dist[v][used] where used in {0,1}
27
    vector<array<long long,2>> dist(n + 1, {INF, INF});
28
    dist[s][0] = 0;
29
30
    using State = tuple<long long,int,int>; // (dist, node, used)
31
    priority_queue<State, vector<State>, greater<State>> pq;
32
    pq.push({0LL, s, 0});
33
34
    while (!pq.empty()) {
35
        auto [d, u, used] = pq.top(); pq.pop();
36
        if (d != dist[u][used]) continue; // stale
37
        for (auto [v, w] : g[u]) {
38
            // 1) Move without coupon usage
39
            if (dist[v][used] > d + w) {
40
                dist[v][used] = d + w;
41
                pq.push({dist[v][used], v, used});
42
            }
43
            // 2) If coupon not used yet, traverse this edge for free
44
            if (used == 0 && dist[v][1] > d) {
45
                dist[v][1] = d;
46
                pq.push({dist[v][1], v, 1});
47
            }
48
        }
49
    }
50
51
    long long ans = min(dist[t][0], dist[t][1]);
52
    cout << (ans >= INF/2 ? -1 : ans) << "\n";
53
    return 0;
54
}
55