Submission #492651

#	Time	Username	Problem	Language	Result	Execution time	Memory
492651		leu_naut	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	601 ms	35432 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define FORd(i,a,b) for (int i = a; i >= b; --i)
#define pii pair <ll,ll>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define tri pair <ll,pii>
#define f first
#define s second

const int N = 2e5;
const int MOD = 1e9 + 7;
const ll oo = 1e18;

vector <pii> g[N + 5];
ll Du[N + 5], Dv[N + 5], ans = LLONG_MAX, D[N + 5], vs[N + 5], dp[2][N + 5],n;

void dijsktra_u(int x)
{
    memset(vs,0,sizeof(vs));
    for (int i = 1; i <= n; ++i) Du[i] = oo;
    Du[x] = 0;
    priority_queue <pii> q;
    q.push(pii(0,x));
    while (!q.empty()) {
        ll u,w;
        tie(w,u) = q.top();
        q.pop();
        if (!vs[u]) {
            vs[u] = 1;
            Du[u] = -w;
            for (auto i : g[u]) q.push(pii(w - i.s,i.f));
        }
    }
}

void dijsktra_v(int x)
{
    memset(vs,0,sizeof(vs));
    for (int i = 1; i <= n; ++i) Dv[i] = oo;
    Dv[x] = 0;
    priority_queue <pii> q;
    q.push(pii(0,x));
    while (!q.empty()) {
        ll u,w;
        tie(w,u) = q.top();
        q.pop();
        if (!vs[u]) {
            vs[u] = 1;
            Dv[u] = -w;
            for (auto i : g[u]) q.push(pii(w - i.s, i.f));
        }
    }
}

void dijsktra(int x, int y)
{
    memset(vs,0,sizeof(vs));
    FOR(i,0,n) dp[0][i] = oo, dp[1][i] = oo, D[i] = oo;
    D[x] = 0;
    priority_queue <tri> q;
    q.push(tri(0,pii(x,0)));
    while (!q.empty()) {
        ll w,u,par;
        pii z;
        tie(w,z) = q.top();
        q.pop();
        tie(u,par) = z;
        if (!vs[u]) {
            vs[u] = 1;
            D[u] = -w;
            dp[0][u] = min(Du[u], dp[0][par]);
            dp[1][u] = min(Dv[u], dp[1][par]);
            for (auto i : g[u])
                q.push(tri(w - i.s, pii(i.f,u)));
        }
        else if (D[u] == -w) {
            ll tmp1 = min(Du[u], dp[0][par]), tmp2 = min(Dv[u], dp[1][par]);
            if (tmp1 + tmp2 <= dp[0][u] + dp[1][u]) {
                dp[0][u] = min(dp[0][par],tmp1);
                dp[1][u] = min(dp[1][par],tmp2);
            }
        }
    }
    ans = min(ans, dp[0][y] + dp[1][y]);
}

int main()
{

    FastIO
    ll m,s,t,u,v;
    cin >> n >> m >> s >> t >> u >> v;
    FOR(i,1,m)
    {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back(pii(v,w));
        g[v].push_back(pii(u,w));
    }
    dijsktra_u(u);
    dijsktra_v(v);
    ans = min(ans, Du[v]);
    dijsktra(s,t);
    //cout << dp[0][5] << ' ' << dp[1][5] << '\n';
    dijsktra(t,s);
    cout << ans;
}

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