Submission #1084206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084206		votranngocvy	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	260 ms	24096 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define NAME "task"
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
vector<pii>g[N];
vector<int>distU(N,inf),distV(N,inf);
int dist[N],dpU[N],dpV[N],n,m;

void dijkstra(int s,vector<int> &dist) {
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,s});
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.top().se,c = q.top().fi;
        q.pop();
        if (dist[u] != c) continue;
        for (auto x: g[u]) {
            int v = x.fi,w = x.se;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({dist[v],v});
            } 
        }
    }
}

int calc(int s,int t) {
    for (int i = 1; i <= n; i++) dist[i] = dpU[i] = dpV[i] = inf;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    dist[s] = 0,dpU[s] = distU[s],dpV[s] = distV[s];
    q.push({0,s});
    while (!q.empty()) {
        int u = q.top().se,c = q.top().fi;
        q.pop();
        if (dist[u] != c) continue;
        for (auto x: g[u]) {
            int v = x.fi,w = x.se;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                dpU[v] = min(distU[v],dpU[u]);
                dpV[v] = min(distV[v],dpV[u]);
                q.push({dist[v],v});
            }
            else if (dist[v] == dist[u] + w && min(distU[v],dpU[u]) + min(distV[v],dpV[u]) <= dpU[v] + dpV[v]) {
                dpU[v] = min(distU[v],dpU[u]);
                dpV[v] = min(distV[v],dpV[u]);
            }
        }
    }
    return dpU[t] + dpV[t];
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int s,t,u,v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dijkstra(u,distU);
    dijkstra(v,distV);
    cout << min({distU[v],calc(s,t),calc(t,s)}) << "\n";
}

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