Submission #1166240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166240		chikien2009	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	267 ms	15512 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

inline void setup()
{
// #ifndef ONLINE_JUDGE
//     freopen("test.inp", "r", stdin);
//     freopen("test.out", "w", stdout);
// #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, a, b, c, s, t, u, v;
priority_queue<pair<long long, int>> pq;
vector<pair<int, int>> g[100000];
long long rs[100000], rt[100000], ru[100000], rv[100000], mu[100000], mv[100000], res;
bool check[100000];

inline void Dijkstra(int root, long long (&dist)[100000])
{
    int cur_node;
    long long cur_dist;
    fill_n(dist, 100000, 1e18);
    dist[root] = 0;
    pq.push({0, root});
    while (!pq.empty())
    {
        cur_node = pq.top().second;
        cur_dist = -pq.top().first;
        pq.pop();
        if (cur_dist != dist[cur_node])
        {
            continue;
        }
        for (auto & i : g[cur_node])
        {
            if (cur_dist + i.second < dist[i.first])
            {
                dist[i.first] = cur_dist + i.second;
                pq.push({-dist[i.first], i.first});
            }
        }
    }
}

int main()
{
    setup();

    cin >> n >> m >> s >> t >> u >> v;
    s--;
    t--;
    u--;
    v--;
    while (m--)
    {
        cin >> a >> b >> c;
        g[a - 1].push_back({b - 1, c});
        g[b - 1].push_back({a - 1, c});
    }
    Dijkstra(s, rs);
    Dijkstra(t, rt);
    Dijkstra(u, ru);
    Dijkstra(v, rv);
    res = ru[v];
    for (int i = 0; i < n; ++i)
    {
        pq.push({-rs[i], i});
    }
    while (!pq.empty())
    {
        a = pq.top().second;
        pq.pop();
        if (rs[a] + rt[a] != rs[t])
        {
            continue;
        }
        mu[a] = ru[a];
        mv[a] = rv[a];
        check[a] = true;
        for (auto & i : g[a])
        {
            if (check[i.first] && rs[a] == rs[i.first] + i.second)
            {
                mu[a] = min(mu[a], mu[i.first]);
                mv[a] = min(mv[a], mv[i.first]);
            }
        }
        res = min({res, mu[a] + rv[a], mv[a] + ru[a]});
    }
    cout << res;
    return 0;
}

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