Chain Rule

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5typedef long long ll;
    6ll INF = INT_MAX;
    7 
    8 
    9int main(){
    10    ios::sync_with_stdio(0);
    11    cin.tie(0);
    12    int n, m;
    13    cin >> n >> m;
    14    vector<vector<pair<int, int>>> adj(n);
    15    for(int i = 0; i < m; i++){
    16        int u, v, w;
    17        cin >> u >> v >> w;
    18        adj[u].push_back({w, v});
    19        adj[v].push_back({w, u});
    20    }
    21    vector<int> dist1(n, INF), dist2(n, INF);
    22    int s1 = 0, s2 = n - 1;
    23    dist1[s1] = 0; dist2[s2] = 0;
    24    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq1, pq2;
    25    pq1.push({0, s1}); pq2.push({0, s2});
    26    while(!pq1.empty()){
    27        auto[d, u] = pq1.top(); pq1.pop();
    28        if(d > dist1[u]) continue;
    29        for(auto[w_u_v, v] : adj[u]){
    30            int v_cost = dist1[u] + w_u_v;
    31            if(v_cost < dist1[v]){
    32                dist1[v] = v_cost;
    33                pq1.push({v_cost, v});
    34            }
    35        }
    36    }
    37    while(!pq2.empty()){
    38        auto[d, u] = pq2.top(); pq2.pop();
    39        if(d > dist2[u]) continue;
    40        for(auto[w_u_v, v] : adj[u]){
    41            int v_cost = dist2[u] + w_u_v;
    42            if(v_cost < dist2[v]){
    43                dist2[v] = v_cost;
    44                pq2.push({v_cost, v});
    45            }
    46        }
    47    }
    48    int ans = 0;
    49    for(int i = 0; i < dist1.size(); i++){
    50        ans = max(ans, dist1[i] + dist2[i]);
    51    }
    52    cout << ans << '\n';
    53    return 0;
    54}