Submission #286080

#	Time	Username	Problem	Language	Result	Execution time	Memory
286080		glikcakbn	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1201 ms	57364 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<int> agph[101010];
vector<int> bgph[101010];
bool vst[101010];
long long dist[101010];
long long dst[101010][4];
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);
        bgph[y].push_back(x);
        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});
        gph[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}});
        }
        dfs(t);
    }

    for(int i = 0; i < n; ++i) for(int j = 0; j < 4; ++j) dst[i][j] = -1;
    priority_queue<plll, vector<plll>, greater<plll>> Q;
    Q.push({0, {u, 0}});
    while(Q.size())
    {
        auto x = Q.top(); Q.pop();
        if(dst[x.ee][x.rr] != -1) continue;
        dst[x.ee][x.rr] = x.ff;

        if(x.rr == 0)
        {
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 0}});
            for(auto y : agph[x.ee]) Q.push({x.ff, {y, 1}});
            for(auto y : bgph[x.ee]) Q.push({x.ff, {y, 2}});
        }
        else if(x.rr == 1)
        {
            for(auto y : agph[x.ee]) Q.push({x.ff, {y, 1}});
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
        }
        else if(x.rr == 2)
        {
            for(auto y : bgph[x.ee]) Q.push({x.ff, {y, 2}});
            for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
        }
        else for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, 3}});
    }

    long long ans = (long long)8e18;
    for(int i = 0; i < 4; ++i) if(dst[v][i] != -1) ans = min(ans, dst[v][i]);
    cout << ans;
}

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