Submission #286063

#	Time	Username	Problem	Language	Result	Execution time	Memory
286063		glikcakbn	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	917 ms	53928 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

vector<pii> gph[101010];
vector<pii> agph[101010];
vector<pii> bgph[101010];
bool vst[101010];
long long dist[101010];
vector<int> pr[101010];

void dfs(int x)
{
    if(vst[x]) return;
    vst[x] = true;
    for(auto y : pr[x]) if(y != -1)
    {
        agph[x].push_back({y, 0});
        bgph[y].push_back({x, 0});
        dfs(y);
    }
}

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

    int n, m; cin >> n >> m;
    int s, t, u, v; cin >> s >> t >> u >> v; --s; --t; --u; --v;
    for(int i = 0; i < m; ++i)
    {
        int s, e, x; cin >> s >> e >> x; --s; --e;
        gph[s].push_back({e, x});
        agph[s].push_back({e, x});
        bgph[s].push_back({e, x});
        gph[e].push_back({s, x});
        agph[e].push_back({s, x});
        bgph[e].push_back({s, x});
    }

    {
        for(int i = 0; i < n; ++i) dist[i] = -1;
        priority_queue<plll, vector<plll>, greater<plll>> Q;
        Q.push({0, {s, -1}});
        while(Q.size())
        {
            auto x = Q.top(); Q.pop();
            if(dist[x.ee] == -1 || dist[x.ee] == x.ff) pr[x.ee].push_back(x.rr);
            if(dist[x.ee] != -1) continue;
            dist[x.ee] = x.ff;
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, x.ee}});
        }

//        for(int i = 0; i < n; ++i)
//        {
//            for(auto x : pr[i]) cout << x << ' ';
//            cout << endl;
//        }

        dfs(t);
    }

    long long ans;
    {
        for(int i = 0; i < n; ++i) dist[i] = -1;
        priority_queue<pll, vector<pll>, greater<pll>> Q;
        Q.push({0, u});
        while(Q.size())
        {
            auto x = Q.top(); Q.pop();
            if(dist[x.ss] != -1) continue;
            dist[x.ss] = x.ff;
            for(auto y : agph[x.ss]) Q.push({x.ff + y.ss, y.ff});
        }
        ans = dist[v];
    }

    {
        for(int i = 0; i < n; ++i) dist[i] = -1;
        priority_queue<pll, vector<pll>, greater<pll>> Q;
        Q.push({0, u});
        while(Q.size())
        {
            auto x = Q.top(); Q.pop();
            if(dist[x.ss] != -1) continue;
            dist[x.ss] = x.ff;
            for(auto y : bgph[x.ss]) Q.push({x.ff + y.ss, y.ff});
        }
        ans = min(ans, dist[v]);
    }

    cout << ans;
}

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