Submission #1166237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166237		chikien2009	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	317 ms	14832 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], processed[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];
    pq.push({s, 0});
    check[s] = true;
    while (!pq.empty())
    {
        a = pq.top().second;
        pq.pop();
        mu[a] = ru[a];
        mv[a] = rv[a];
        processed[a] = true;
        for (auto & i : g[a])
        {
            if (rs[i.first] + rt[i.first] == rs[t])
            {
                if (processed[i.first])
                {
                    if (rs[i.first] + i.second == rs[a])
                    {
                        mu[a] = min(mu[a], mu[i.first]);
                        mv[a] = min(mv[a], mv[i.first]);
                    }
                }
                else if (!check[i.first])
                {
                    pq.push({-rs[i.first], i.first});
                    check[i.first] = true;
                }
            }
        }
        res = min({res, mu[a] + rv[a], mv[a] + ru[a]});
    }
    cout << res;
    return 0;
}

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