Submission #1093331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093331		KindaGoodGames	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	2065 ms	133364 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();
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});
        }
    }

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

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

    // 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});
        }
    }
    cout << dist2[vg] <<endl;
}

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