Submission #1163786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163786		canhnam357	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	198 ms	28684 KiB

commuter_pass

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
    f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
    f = (f < s ? f : s);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int s, t, u, v;
    cin >> s >> t >> u >> v;
    s--, t--, u--, v--;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }   
    vector<int> d1(n, inf), d2(n, inf);
    {
        priority_queue<pair<int, int>> q;
        d1[s] = 0;
        q.emplace(0, s);
        while (!q.empty())
        {
            auto [dis, a] = q.top();
            q.pop();
            dis = -dis;
            if (dis != d1[a]) continue;
            for (auto [b, c] : adj[a])
            {
                int nd = c + dis;
                if (nd < d1[b])
                {
                    d1[b] = nd;
                    q.emplace(-nd, b);
                }
            }
        }
    }
    {
        priority_queue<pair<int, int>> q;
        d2[t] = 0;
        q.emplace(0, t);
        while (!q.empty())
        {
            auto [dis, a] = q.top();
            q.pop();
            dis = -dis;
            if (dis != d2[a]) continue;
            for (auto [b, c] : adj[a])
            {
                int nd = c + dis;
                if (nd < d2[b])
                {
                    d2[b] = nd;
                    q.emplace(-nd, b);
                }
            }
        }
    }
    vector<vector<int>> d(n, vector<int>(2, inf));
    d[u][0] = d[u][1] = 0;
    priority_queue<tuple<int, int, int>> q;
    q.emplace(0, u, 0);
    q.emplace(0, u, 1);
    while (!q.empty())
    {
        auto [dis, a, k] = q.top();
        q.pop();
        dis = -dis;
        if (dis != d[a][k]) continue;
        for (auto [b, c] : adj[a])
        {
            if (d1[a] + c + d2[b] == d1[t] && k == 0)
            {
                int nd = dis;
                if (nd < d[b][k])
                {
                    d[b][k] = nd;
                    q.emplace(-nd, b, k);
                }
            }
            else if (d1[b] + c + d2[a] == d1[t] && k == 1)
            {
                int nd = dis;
                if (nd < d[b][k])
                {
                    d[b][k] = nd;
                    q.emplace(-nd, b, k);
                }
            }
            else
            {
                int nd = c + dis;
                if (nd < d[b][k])
                {
                    d[b][k] = nd;
                    q.emplace(-nd, b, k);
                }
            }
        }
    }
    cout << min(d[v][0], d[v][1]);
    return 0;
}

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