Submission #1179137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179137		MongHwa	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	178 ms	28748 KiB

commuter_pass

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
using namespace std;

#define ll long long
#define INF 1e17
#define X first
#define Y second

vector<pair<int, int>> stage[100005];
vector<ll> sdist, udist, vdist;
bool status[100005];
queue<int> q;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
multiset<ll> ums, vms;
set<int> path, blocked;

void dijkstra(vector<ll>& dist, int s)
{
    fill(dist.begin(), dist.end(), INF);
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty())
    {
        ll d; int cur;
        tie(d, cur) = pq.top(); pq.pop();

        if(dist[cur] != d)
            continue;
        
        for(auto& nxt : stage[cur])
            if(dist[nxt.X] > d + nxt.Y)
            {
                dist[nxt.X] = d + nxt.Y;
                pq.push({dist[nxt.X], nxt.X});
            }
    }
}

void dfs(int cur, ll& ans)
{
    ums.insert(udist[cur]);
    vms.insert(vdist[cur]);
    ans = min(ans, *ums.begin()+*vms.begin());

    int tmp = 0;
    for(auto& nxt : stage[cur])
        if(sdist[nxt.X] + nxt.Y == sdist[cur])
            tmp++;
    
    if(tmp > 1)
    {
        int pre = -1;
        for(int i = 0; i < (int)stage[cur].size(); i++)
        {
            auto& val = stage[cur][i];
            if(sdist[val.X] + val.Y == sdist[cur])
            {
                path.clear();
                blocked.clear();
                q.push(val.X);
                path.insert(val.X);
                while(!q.empty())
                {
                    int elem = q.front(); q.pop();
                    ums.insert(udist[elem]);
                    vms.insert(vdist[elem]);

                    for(auto& nxt : stage[elem])
                        if(sdist[nxt.X] + nxt.Y == sdist[elem])
                        {
                            if(path.count(nxt.X))
                                continue;
                            else if(!status[nxt.X])
                            {
                                q.push(nxt.X);
                                path.insert(nxt.X);
                            }
                            else
                                blocked.insert(nxt.X);
                        }
                }

                if(pre != -1)
                {
                    q.push(pre);
                    status[pre] = 0;
                    ums.erase(ums.find(udist[pre]));
                    vms.erase(vms.find(vdist[pre]));
                    while(!q.empty())
                    {
                        int elem = q.front(); q.pop();

                        for(auto& nxt : stage[elem])
                            if(sdist[nxt.X] + nxt.Y == sdist[elem] && !blocked.count(nxt.X) && status[nxt.X])
                            {
                                status[nxt.X] = 0;
                                ums.erase(ums.find(udist[elem]));
                                vms.erase(vms.find(vdist[elem]));
                                q.push(nxt.X);
                            }
                    }
                }

                ans = min(ans, *ums.begin()+*vms.begin());
                pre = val.X;
                for(int x : path)
                    status[x] = 1;
            }
        }
        
        return;
    }
    else
    {
        for(auto& nxt : stage[cur])
            if(sdist[nxt.X] + nxt.Y == sdist[cur])
                dfs(nxt.X, ans);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;

        stage[a].push_back({b, c});
        stage[b].push_back({a, c});
    }

    sdist.resize(n+1); udist.resize(n+1); vdist.resize(n+1);
    dijkstra(sdist, s);
    dijkstra(udist, u);
    dijkstra(vdist, v);

    ll ans = udist[v];
    dfs(t, ans);

    cout << ans << '\n';
}

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