Submission #1093436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093436		KindaGoodGames	Robot (JOI21_ho_t4)	C++14	0 / 100	1 ms	1628 KiB

Main

/*
    Need to consider bidirectional path option.

    Idea was right, just implementation doesn't work :(
*/

#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){
// Shortest paths from s to t
    vector<int> dist(n,INF);
    vector<set<int>> pre(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(dist[v] < d) continue; 
        pre[v].insert(p);
        if(dist[v] == d) continue;
        dist[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 Graph
    vector<vector<int>> adjSP(n);
    vector<bool> vis(n);
    queue<int> qp;
    qp.push(t);
    while(qp.size()){
        int i = qp.front();
        qp.pop();
        if(vis[i]) continue;
        vis[i] = true;
        for(auto u : pre[i]){
            adjSP[i].push_back(u);
            //adjSP[u].push_back(i);
            if(!vis[u])qp.push(u);
        }
    }
    // 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});
        }
    }


    // do the same thing but other way around
    used.clear();
    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(){
    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});
    }

    // Subcase 1

    cout << min({result(n,m,s,t,ug,vg,adj),result(n,m,t,s,vg,ug,adj)}) << endl; 
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42