Submission #1167938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167938		diana	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	189 ms	25164 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC oprimize("O3, unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define edge pair<ll, int>
#define c first
#define vi second
using namespace std;

typedef long long ll;

const int N = 1e5+5;
const ll M = 1e18;
int n, m, s, t, u, v;
vector<edge> graf[N];

class vertex
{
private:
    int v;
    vector<ll> dist;
    bool dw;
    void dijkstra()
    {
        if(dw)
            return;
        dist.assign(n+5, M);
        priority_queue<edge, vector<edge>, greater<edge>> pq;
        bool vis[n] = {};
        pq.push({0, v});
        dist[v] = 0;
        while(!pq.empty())
        {
            edge t = pq.top(); pq.pop();
            if(vis[t.vi])
                continue;
            vis[t.vi] = 1;
            for(auto x: graf[t.vi])
            {
                if(t.c + x.c < dist[x.vi])
                {
                    pq.push({t.c + x.c, x.vi});
                    dist[x.vi] = t.c + x.c;
                }
            }
        }
    }
public:
    vertex(int a)
    {
        v = a;
        dw = 0;
    }

    ll distto_a(int a)
    {
        if(!dw)
        {
            dijkstra();
            dw = 1;
        }
        return dist[a];
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

    vector<vertex> ver;

    s--; t--; u--; v--;
    for(int i=0; i<n; i++)
    {
        vertex a(i);
        ver.push_back(a);
    }

    while(m--)
    {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        graf[a].push_back({c, b});
        graf[b].push_back({c, a});
    }

    ll gc = ver[s].distto_a(t);
    ll ans=ver[u].distto_a(v);
    ll mv[n], mu[n];

    vector<edge> hm;

    for(int i=0; i<n; i++)
    {
        if(ver[s].distto_a(i)+ver[t].distto_a(i) == gc)
            hm.push_back({ver[s].distto_a(i), i});
        mv[i] = M;
        mu[i] = M;
    }
    sort(hm.begin(), hm.end(), greater<edge>());

    for(auto x: hm)
    {
        mv[x.vi] = ver[v].distto_a(x.vi);
        mu[x.vi] = ver[u].distto_a(x.vi);
        ans = min(ans, mv[x.vi]+mu[x.vi]);
        for(auto y: graf[x.vi])
        {
            if(ver[s].distto_a(y.vi) + ver[t].distto_a(y.vi) != gc)
                continue;
            if(ver[s].distto_a(y.vi) - y.c != x.c)
                continue;

            ans = min(ans, min(ver[v].distto_a(x.vi)+mu[y.vi],
                               ver[u].distto_a(x.vi)+mv[y.vi]));
            mv[x.vi] = min(mv[x.vi], mv[y.vi]);
            mu[x.vi] = min(mu[x.vi], mu[y.vi]);
        }
   }

    cout << ans;
    return 0;
}

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