Submission #1241945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241945		trantien3771	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	130 ms	24840 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int maxn = 2e5 + 5;
const int mod = 11229837253;

using namespace std;

int n, m, a, b, c, d, r[maxn], trace[maxn];
vector<pii> ke[maxn];

void dijktra1(int s){
    for (int i = 1; i <= n; i++) r[i] = 1e18;
    r[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, s});
    while (!pq.empty()){
        int u = pq.top().se;
        int kc = pq.top().fi;
        pq.pop();
        if (kc > r[u]) continue;
        for (auto [v, x] : ke[u]){
            if (r[v] > r[u] + x){
                r[v] = r[u] + x;
                pq.push({r[v], v});
                trace[v] = u;
            }
        }
    }
}



main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> a >> b >> c >> d;
    for (int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        ke[u].pb({v, w});
        ke[v].pb({u, w});
    }

    dijktra1(a);
    int x = trace[b];
    ke[b].pb({x, 0});
    ke[x].pb({b, 0});
    while (x != 0){
        int cur = x;
        x = trace[x];
        ke[cur].pb({x, 0});
        ke[x].pb({cur, 0});
    }

    dijktra1(c);
    cout << r[d];

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

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