Submission #1090941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090941		chautanphat	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	238 ms	24288 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1;
int n, m, s, t, u, v;
long long ans;
vector<pair<int, int>> a[N];
vector<int> g[N];
vector<long long> ds, dt, du, dv, dp1(N, 1e16), dp2(N, 1e16);
bool vs[N];

vector<long long> dijkstra(int s)
{
    vector<long long> d(n+1, 1e16);
    priority_queue<pair<long long, int>> q;
    d[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        long long dis = -q.top().first;
        int u = q.top().second;
        q.pop();
        if (d[u] != dis) continue;
        for (int i = 0; i < (int)a[u].size(); i++)
        {
            int v = a[u][i].first, w = a[u][i].second;
            if (d[u]+w < d[v])
            {
                d[v] = d[u]+w;
                q.push({-d[v], v});
            }
        }
    }
    return d;
}

pair<long long, long long> dfs(int u)
{
    if (vs[u]) return {dp1[u], dp2[u]};
    vs[u] = 1, dp1[u] = dv[u], dp2[u] = du[u];
    for (int i = 0; i < (int)g[u].size(); i++)
    {
        int v = g[u][i];
        pair<long long, long long> p = dfs(v);
        dp1[u] = min(dp1[u], p.first);
        dp2[u] = min(dp2[u], p.second);
    }
    ans = min(ans, min(du[u]+dp1[u], dv[u]+dp2[u]));
    return {dp1[u], dp2[u]};
}

int main()
{    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> s >> t >> u >> v;

    while (m--)
    {
        int u, v, c;
        cin >> u >> v >> c;
        a[u].push_back({v, c});
        a[v].push_back({u, c});
    }

    ds = dijkstra(s);
    dt = dijkstra(t);
    du = dijkstra(u);
    dv = dijkstra(v);
    ans = du[v];

    for (int u = 1; u <= n; u++)
        for (int i = 0; i < (int)a[u].size(); i++)
            if (ds[u]+a[u][i].second+dt[a[u][i].first] == ds[t])
                g[u].push_back(a[u][i].first);

    for (int i = 1; i <= n; i++)
        if (!vs[i]) dfs(i);
    
    cout << ans;

    return 0;
}

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