Submission #1318672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318672		vuviet	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	374 ms	23352 KiB

commuter_pass

/**
 *     Author:       trviet
 *     Studies at:   Le Hong Phong High School for the Gifted
**/

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

constexpr int maxn = 2e5 + 5;
constexpr long long inf = 1e18;

int n, m, src[4], mark[maxn];
lli d[4][maxn], ans = inf, dp[maxn][2];
vector<pair<int, int>> g[maxn];
vector<int> dag[maxn];

void Dijkstra(int k)
{
    fill(d[k], d[k] + 1 + n, inf);
    priority_queue<pair<lli, int>> pq;
    pq.push({0, src[k]});
    d[k][src[k]] = 0;
    while (!pq.empty())
    {
        int x = pq.top().second;
        pq.pop();
        for (int i = 0; i < g[x].size(); ++i)
        {
            int y = g[x][i].first, w = g[x][i].second;
            if (d[k][y] > d[k][x] + w)
            {
                d[k][y] = d[k][x] + w;
                pq.push({-d[k][y], y});
            }
        }
    }
}

void depth_search(int u)
{
    if (mark[u]) return;
    mark[u] = 1, dp[u][0] = dp[u][1] = inf;
    for (int v : dag[u])
    {
        depth_search(v);
        dp[u][0] = min(dp[u][0], min(dp[v][0], d[2][v]));
        dp[u][1] = min(dp[u][1], min(dp[v][1], d[3][v]));
    }
    ans = min(ans, dp[u][0] + d[3][u]);
    ans = min(ans, dp[u][1] + d[2][u]);
}

void ReadData()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < 4; ++i)
        cin >> src[i];
    for (int i = 0; i < m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
}

void Solve()
{
    for (int i = 0; i < 4; ++i)
        Dijkstra(i);
    for (int i = 1; i <= n; ++i)
        for (int t = 0; t < g[i].size(); ++t)
        {
            int j = g[i][t].first, w = g[i][t].second;
            if (d[0][i] + w + d[1][j] == d[0][src[1]])
                dag[i].push_back(j);
        }
    depth_search(src[0]);
    cout << min(d[2][src[3]], ans);
}

int main()
{
    ReadData();
    Solve();
    return 0;
}

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