Submission #833843

#	Time	Username	Problem	Language	Result	Execution time	Memory
833843		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	280 ms	22560 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

using namespace std;

const ll inf = 1e17;
const int ar = 1e5 + 5;
const int mod = 1e9 + 7;

int n, m, s, t, u, v;
vector<pii> a[ar];
vector<ll> vv(ar, inf), ss(ar, inf), uu(ar, inf), tt(ar, inf);
vector<ll> u1(ar, inf), u2(ar, inf), v1(ar, inf), v2(ar, inf);

void dijkstra(ll s, vector<ll> &d)
{
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    Q.push({0, s});
    while (!Q.empty())
    {
        pii Top = Q.top();
        Q.pop();
        ll u = Top.se, kc = Top.fi;
        if (kc > d[u])
            continue;
        for (auto it : a[u])
        {
            ll v = it.fi, w = it.se;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push({d[v], v});
            }
        }
    }
}

void dijkstra2(ll s, vector<ll> &d)
{
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    Q.push({0, s});
    while (!Q.empty())
    {
        pii Top = Q.top();
        Q.pop();
        ll u = Top.se, kc = Top.fi;
        if (kc > d[u])
            continue;
        for (auto it : a[u])
        {
            ll v = it.fi, w = it.se;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push({d[v], v});
                u2[v] = min(u2[u], uu[v]);
                v2[v] = min(v2[u], vv[v]);
            }
        }
    }
}

void dijkstra1(ll s, vector<ll> &d)
{
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    Q.push({0, s});
    while (!Q.empty())
    {
        pii Top = Q.top();
        Q.pop();
        ll u = Top.se, kc = Top.fi;
        if (kc > d[u])
            continue;
        for (auto it : a[u])
        {
            ll v = it.fi, w = it.se;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push({d[v], v});
                u1[v] = min(u1[u], uu[v]);
                v1[v] = min(v1[u], vv[v]);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        a[x].push_back({y, w});
        a[y].push_back({x, w});
    }
    dijkstra(u, uu);
    dijkstra(v, vv);
    for (int i = 1; i <= n; i++)
    {
        u1[i] = u2[i] = uu[i];
        v1[i] = v2[i] = vv[i];
    }
    dijkstra1(s, ss);
    dijkstra2(t, tt);
    ll ans = uu[v];
    for (int i = 1; i <= n; i++)
        if (ss[i] + tt[i] == ss[t])
            ans = min({ans, u1[i] + v2[i], u2[i] + v1[i]});
    cout << ans;
    return 0;
}

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