Submission #833980

#	Time	Username	Problem	Language	Result	Execution time	Memory
833980		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	264 ms	31120 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define piii pair<long long, long long>
using ll = long long;
const ll nmax = 2e5 + 5;
const ll mod = 1e9 + 7;

int n, m, u, v, s, t;
ll ans;
long long uu[nmax], vv[nmax], u1[nmax], v1[nmax], ss[nmax], tt[nmax], u2[nmax], v2[nmax];
vector<piii> edge[nmax];

void dijkstra(ll u)
{
    memset(uu, 0x3f, sizeof(uu));
    uu[u] = 0;
    priority_queue<piii, vector<piii>, greater<piii>> Q;
    Q.push({0, u});
    while (!Q.empty())
    {
        piii top = Q.top();
        Q.pop();
        ll u = top.second;
        ll kc = top.first;
        if (kc > uu[u])
            continue;
        for (auto it : edge[u])
        {
            ll v = it.first;
            ll w = it.second;
            if (uu[v] > uu[u] + w)
            {
                uu[v] = uu[u] + w;
                Q.push({uu[v], v});
            }
        }
    }
}
void dijkstra2(ll u)
{
    memset(vv, 0x3f, sizeof(vv));
    vv[u] = 0;
    priority_queue<piii, vector<piii>, greater<piii>> Q;
    Q.push({0, u});
    while (!Q.empty())
    {
        piii top = Q.top();
        Q.pop();
        ll u = top.second;
        ll kc = top.first;
        if (kc > vv[u])
            continue;
        for (auto it : edge[u])
        {
            ll v = it.first;
            ll w = it.second;
            if (vv[v] > vv[u] + w)
            {
                vv[v] = vv[u] + w;
                Q.push({vv[v], v});
            }
        }
    }
}
void dijkstra3(ll u)
{
    memset(ss, 0x3f, sizeof(ss));
    memset(u1, 0x3f, sizeof(u1));
    memset(v1, 0x3f, sizeof(v1));
    ss[u] = 0;
    u1[u] = uu[u];
    v1[u] = vv[u];
    priority_queue<piii, vector<piii>, greater<piii>> Q;
    Q.push({0, u});
    while (!Q.empty())
    {
        piii top = Q.top();
        Q.pop();
        ll u = top.second;
        ll kc = top.first;
        if (kc > ss[u])
            continue;
        for (auto it : edge[u])
        {
            ll v = it.first;
            ll w = it.second;
            if (ss[v] > ss[u] + w)
            {
                ss[v] = ss[u] + w;
                u1[v] = min(u1[u], uu[v]);
                v1[v] = min(v1[u], vv[v]);
                Q.push({ss[v], v});
            }
            else if (ss[v] == ss[u] + w)
            {
                u1[v] = min(u1[u], u1[v]);
                v1[v] = min(v1[u], v1[v]);
            }
        }
    }
}
void dijkstra4(ll u)
{
    memset(tt, 0x3f, sizeof(tt));
    memset(u2, 0x3f, sizeof(u2));
    memset(v2, 0x3f, sizeof(v2));
    tt[u] = 0;
    u2[u] = uu[u];
    v2[u] = vv[u];
    priority_queue<piii, vector<piii>, greater<piii>> Q;
    Q.push({0, u});
    while (!Q.empty())
    {
        piii top = Q.top();
        Q.pop();
        ll u = top.second;
        ll kc = top.first;
        if (kc > tt[u])
            continue;
        for (auto it : edge[u])
        {
            ll v = it.first;
            ll w = it.second;
            if (tt[v] > tt[u] + w)
            {
                tt[v] = tt[u] + w;
                u2[v] = min(u2[u], uu[v]);
                v2[v] = min(v2[u], vv[v]);
                Q.push({tt[v], v});
            }
            else if (tt[v] == tt[u] + w)
            {
                u2[v] = min(u2[u], u2[v]);
                v2[v] = min(v2[u], v2[v]);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for (ll i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }
    dijkstra(u);
    dijkstra2(v);
    dijkstra3(s);
    dijkstra4(t);
    ans = uu[v];
    for (int i = 1; i <= n; ++i)
        if (ss[i] + tt[i] == ss[t])
            ans = min({ans, u1[i] + v2[i], v1[i] + u2[i]});
    cout << ans;
}

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