Submission #772800

#	Time	Username	Problem	Language	Result	Execution time	Memory
772800		1bin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	279 ms	23996 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
ll n, m, S, T, U, V, a, b, c, dist[NMAX], ans, cost[NMAX], C1[NMAX], C2[NMAX], vis[NMAX];
vector<pair<int, ll>> adj[NMAX];

void dijk(int s){
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pair<ll, ll>> pq;
    pq.emplace(0, s); dist[s] = 0;
    while(pq.size()){
        auto[d, x] = pq.top(); pq.pop();
        d = -d;
        if(d > dist[x]) continue;
        for(auto&[nx, p] : adj[x])
            if(d + p < dist[nx]){
                dist[nx] = d + p;
                pq.emplace(-d-p, nx);
            }
    }
    return;
}

void go(int s, int t){
    dijk(s);
    priority_queue<pair<ll, ll>> pq;
    memset(vis, 0, sizeof(vis));
    pq.emplace(dist[t], t); vis[t] = 1;
    while(pq.size()){
        auto[d, x] = pq.top(); pq.pop();
        for(auto&[nx, p]: adj[x])
            if(d - p == dist[nx]){
                C1[nx] = min(C1[nx], C1[x]);
                if(!vis[nx]) vis[nx] = 1, pq.emplace(d-p, nx);
            }
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> S >> T >> U >> V;
    while(m--){
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }
    dijk(U);
    for(int i = 1; i <= n; i++) C1[i] = C2[i] = dist[i];
    ans = dist[V];
    go(S, T);
    swap(C1, C2);
    go(T, S);
    for(int i = 1; i <= n; i++) cost[i] = min(C1[i], C2[i]);
    dijk(V);
    for(int i = 1; i <= n; i++) ans = min(ans, dist[i] + cost[i]);
    cout << ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(int)':
commuter_pass.cpp:16:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |         auto[d, x] = pq.top(); pq.pop();
      |             ^
commuter_pass.cpp:19:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |         for(auto&[nx, p] : adj[x])
      |                  ^
commuter_pass.cpp: In function 'void go(int, int)':
commuter_pass.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         auto[d, x] = pq.top(); pq.pop();
      |             ^
commuter_pass.cpp:35:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         for(auto&[nx, p]: adj[x])
      |                  ^

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45