Submission #1318578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318578		vuviet	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	198 ms	25072 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using lli = long long;

constexpr int maxn = 2e5 + 5;
vector<pii> g[maxn], adj[maxn];
int n, m, s, t, u, v;

struct Edge
{
    int x, y, w;
} elist[maxn];

vector<lli> Dijkstra(int src, vector<pii> g[maxn])
{
    vector<lli> dp(n + 1, 1e18);
    priority_queue<pair<lli, int>> pq;
    pq.push({0, src});
    dp[src] = 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 (dp[y] > dp[x] + w)
            {
                dp[y] = dp[x] + w;
                pq.push({-dp[y], y});
            }
        }
    }
    return dp;
}

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

void Solve()
{
    vector<lli> d = Dijkstra(s, g), f = Dijkstra(t, g);
    lli D = d[t];
    for (int i = 0; i < m; ++i)
    {
        int x = elist[i].x, y = elist[i].y, w = elist[i].w;
        if (d[x] + w + f[y] == D)
            adj[x].push_back({y, 0});
        if (d[y] + w + f[x] == D)
            adj[y].push_back({x, 0});
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    vector<lli> best = Dijkstra(u, adj);
    cout << best[v];
}

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

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