Submission #655323

#	Time	Username	Problem	Language	Result	Execution time	Memory
655323		benjaminkleyn	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	581 ms	32068 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
vector<pair<int,ll>> g[100001];
bool vis[100001];
vector<int> dag[100001];
vector<ll> distS, distU, distV;

vector<ll> dijkstra(int src)
{
    vector<ll> dist(N + 1, LLONG_MAX);
    for (int u = 1; u <= N; u++)
        vis[u] = false, dag[u] = vector<int>();

    priority_queue<pair<ll, int>> pq;
    dist[src] = 0;
    pq.push({0LL, src});

    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (auto [v, l] : g[u])
            if (dist[u] + l < dist[v])
            {
                dag[v] = {u};
                dist[v] = dist[u] + l;
                pq.push({-dist[v], v});
            }
            else if (dist[v] == dist[u] + l)
                dag[v].push_back(u);
    }

    return dist;
}

ll dpU[100001], dpV[100001];

ll ans = LLONG_MAX;
void dfs(int x)
{
    vis[x] = true;

    dpU[x] = min(dpU[x], distU[x]);
    dpV[x] = min(dpV[x], distV[x]);

    for (int y : dag[x])
    {
        if (!vis[y])
            dfs(y);

        dpU[x] = min(dpU[x], dpU[y]);
        dpV[x] = min(dpV[x], dpV[y]);
    }

    ans = min(ans, distU[x] + dpV[x]);
    ans = min(ans, distV[x] + dpU[x]);
}

int main()
{
    int M, S, T, U, V;
    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 0, a, b; i < M; i++)
    {
        ll c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    distU = dijkstra(U);
    distV = dijkstra(V);
    distS = dijkstra(S);

    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= N; i++)
        dpU[i] = dpV[i] = LLONG_MAX;
    ans = distV[U];
    dfs(T);

    cout << ans << '\n';

    return 0;
}

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