Submission #126510

#	Time	Username	Problem	Language	Result	Execution time	Memory
126510		EntityIT	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	457 ms	23732 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

using ll = long long;
using li = pair<ll, int>;
const int N = (int)1e5 + 5, M = (int)2e5 + 5;
const ll infll = (ll)1e18 + 123;
int n, m, S, T, U, V;
ll ans;
vector< pair<int, int> > gr[N];
vector<int> Gr[N];
vector<ll> dS, dU, dV, dpU, dpV;
vector<bool> vis;

void dijkstra (int src, vector<ll> &d) {
    d.assign(n + 5, infll); d[src] = 0;
    priority_queue<li, vector<li>, greater<li> > pq; pq.push( { d[src], src } );
    while (!pq.empty() ) {
        li tmp = pq.top(); pq.pop();
        int u = tmp.se;
        if (d[u] < tmp.fi) continue ;
        for (auto _ : gr[u]) {
            int v = _.fi, w = _.se;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push( { d[v], v } );
            }
        }
    }
}

ll calc_dpU (int u) {
    if (dpU[u] != -1) return dpU[u];
    dpU[u] = dU[u];
    for (int v : Gr[u]) dpU[u] = min(dpU[u], calc_dpU(v) );
    return dpU[u];
}

ll calc_dpV (int u) {
    if (dpV[u] != -1) return dpV[u];
    dpV[u] = dV[u];
    for (int v : Gr[u]) dpV[u] = min(dpV[u], calc_dpV(v) );
    return dpV[u];
}

void trace (int u) {
    if (vis[u] || u == S) return ;
    vis[u] = 1;
    for (auto _ : gr[u]) {
        int v = _.fi, w = _.se;
        if (dS[v] + w == dS[u]) Gr[v].pb(u), trace(v);
    }
}

void dfs (int u) {
    if (vis[u]) return ;
    vis[u] = 1;
    ans = min(ans, dU[u] + dpV[u]);
    ans = min(ans, dV[u] + dpU[u]);
    for (int v : Gr[u]) dfs(v);
}

int main () {
    scanf("%d %d %d %d %d %d", &n, &m, &S, &T, &U, &V);
    while (m --) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        gr[a].pb( { b, c } );
        gr[b].pb( { a, c } );
    }

    dijkstra(S, dS);
    dijkstra(U, dU);
    dijkstra(V, dV);

    vis.assign(n + 5, 0);
    trace(T);

    dpU.assign(n + 5, -1);
    calc_dpU(S);
    dpV.assign(n + 5, -1);
    calc_dpV(S);

    ans = dU[V];
    vis.assign(n + 5, 0);
    dfs(S);

    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d %d", &n, &m, &S, &T, &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:71:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b, c; scanf("%d %d %d", &a, &b, &c);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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