Submission #1093371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093371		KindaGoodGames	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2056 ms	53028 KiB

commuter_pass

#include<bits/stdc++.h>

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

using namespace std;

ll INF = numeric_limits<ll>::max()/4;
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});
    }


    // 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});
        }
    }

    // remove add help vertices
    queue<tiii> q; set<pii> used;
    int mi = INF;
    // cur | pre
    q.push({t,t, INF});
    while(q.size())
    {
        int v, u, d;
        tie(v,u,d) = q.front();
        q.pop();
        
        //adj[v].push_back({u,0});
        
        mi = min(mi, dist2[v] + d);
        used.insert({v,u});

        int newd = min(d, distVG[v]);
        for(auto w : pre[v]){
            if(!used.count({w,v}) && w != v)q.push({w,v,newd});
            if(!used.count({w,v}) && w != v)q.push({v,w,newd});
        }
    }

    cout << mi <<endl;
}

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