Submission #1093454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093454		KindaGoodGames	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	892 ms	61376 KiB

commuter_pass

/*
    Need to consider bidirectional path option.

    Idea was right, just implementation doesn't work :(
*/
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>

using namespace std;

ll INF = numeric_limits<ll>::max() / 2;

int result(int n, int m, int s, int t, int ug, int vg, vector<vector<pii>>& adj, vector<int>&dist, vector<set<int>>& pre, vector<int>& dist2,vector<int>& distVG, vector<vector<int>>& adjSP) {
    // Shortest paths from s to t
    priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
    
    // remove add help vertices
    queue<tiiii> q; map<pii, int> used;
    int mi = dist2[vg];
    // cur | pre
    q.push({ t,t, INF, INF });
    while (q.size())
    {
        int v, u, d, ds;
        tie(v, u, d, ds) = q.front();
        q.pop();

        //adj[v].push_back({u,0});
        // distance to go from any node in path to the goal
        int newd = min(d, distVG[v]);
        // distance to go to any node in path from start 
        int newds = min(ds, dist2[v]);
        mi = min(mi, newds + newd);
        used[{v, u}]++;

        for (auto w : adjSP[v]) {
            if (used[{w, v}] < 1 && w != v)q.push({ w,v,newd,newds });
            //if(!used.count({v,w}) && w != v)q.push({v,w,newd});
        }
    }


    return min(mi, dist2[vg]);
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;

    int s, t;
    cin >> s >> t;
    s--; t--;

    int ug, vg;
    cin >> ug >> vg;
    ug--; vg--;

    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }

    // Shortest paths from s to t
    vector<int> dists(n, INF);
    vector<set<int>> pres(n);

    priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
    pq.push({ 0,s,s });
    while (pq.size()) {
        int d, v, p;
        tie(d, v, p) = pq.top();
        pq.pop();
        if (dists[v] < d) continue;
        pres[v].insert(p);
        if (dists[v] == d) continue;
        dists[v] = d;

        for (auto pa : adj[v]) {
            pq.push({ pa.second + d, pa.first, v });
        }
    }
    // Shortest paths from t to s
    vector<int> distt(n, INF);
    vector<set<int>> pret(n);

    pq.push({ 0,t,t });
    while (pq.size()) {
        int d, v, p;
        tie(d, v, p) = pq.top();
        pq.pop();
        if (distt[v] < d) continue;
        pret[v].insert(p);
        if (distt[v] == d) continue;
        distt[v] = d;

        for (auto pa : adj[v]) {
            pq.push({ pa.second + d, pa.first, v });
        }
    }

    // run Dijkstra again
    vector<int> dist2(n, INF);
    pq.push({ 0,ug,ug });
    while (pq.size()) {
        int d, v, p;
        tie(d, v, p) = pq.top();
        pq.pop();
        if (dist2[v] <= d) continue;
        dist2[v] = d;

        for (auto pa : adj[v]) {
            pq.push({ pa.second + d, pa.first, v });
        }
    }

    // run Dijkstra again
    vector<int> distVG(n, INF);
    pq.push({ 0,vg,vg });
    while (pq.size()) {
        int d, v, p;
        tie(d, v, p) = pq.top();
        pq.pop();
        if (distVG[v] <= d) continue;
        distVG[v] = d;

        for (auto pa : adj[v]) {
            pq.push({ pa.second + d, pa.first, v });
        }
    }


    // SP ADJ
    
    // SP Graph
    vector<vector<int>> adjSPS(n);
    vector<bool> vis(n);
    queue<int> qp;
    set<pii> us;
    qp.push(t);
    while (qp.size()) {
        int i = qp.front();
        qp.pop();
        if (vis[i]) continue;
        vis[i] = true;
        for (auto u : pres[i]) {
            if(!us.count({i,u})){
                adjSPS[i].push_back(u);
                us.insert({i,u});    
            }
            //adjSP[u].push_back(i);
            if (!vis[u])qp.push(u);
        }
    }
    
    // SP Graph
    vector<vector<int>> adjSPT(n);
    qp = queue<int>();
    us.clear();
    vis = vector<bool>(n);
    qp.push(s);
    while (qp.size()) {
        int i = qp.front();
        qp.pop();
        if (vis[i]) continue;
        vis[i] = true;
        for (auto u : pret[i]) {
            if(!us.count({i,u})){
                adjSPT[i].push_back(u);
                us.insert({i,u});    
            }
            //adjSP[u].push_back(i);
            if (!vis[u])qp.push(u);
        }
    }

    // Subcase 1
    int a = result(n, m, s, t, ug, vg, adj, dists, pres, dist2, distVG, adjSPS); int b = result(n, m, t, s, vg, ug, adj, distt, pret, distVG,dist2, adjSPT);
    int c = result(n, m, t,s , ug, vg, adj, distt, pret, dist2, distVG, adjSPS);
    // int d = result(n, m, s, t, vg ,ug, adj, dists, pres, distVG,dist2 );
    cout << min({ a, b, c}) << "\n";
}

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