Submission #116014

#	Time	Username	Problem	Language	Result	Execution time	Memory
116014		oolimry	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	636 ms	27108 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int s, t, p, q;
    cin >> s >> t >> p >> q;
    s--;
    t--;
    p--;
    q--;

    typedef pair<long long, long long> ii;

    vector<ii> adj[n];

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

    priority_queue<ii, vector<ii>, greater<ii> > dtr;

    long long disp[n];
    long long disq[n];
    long long dis[n];
    long long dist[n];
    fill(disp,disp+n,102345678901234567ll);
    fill(disq,disq+n,102345678901234567ll);
    fill(dis,dis+n,102345678901234567ll);
    fill(dist,dist+n,102345678901234567ll);

    disp[p] = 0;
    dtr.push(ii(0,p));
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(ii nei : adj[cur.second]){
            if(disp[nei.second] > nei.first + cur.first){
                disp[nei.second] = nei.first + cur.first;
                dtr.push(ii(disp[nei.second],nei.second));
            }
        }
    }

    for(int i = 0;i < n;i++){
      //  cout << disp[i] << " ";
    }
   // cout << "\n";


    disq[q] = 0;
    dtr.push(ii(0,q));
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(ii nei : adj[cur.second]){
            if(disq[nei.second] > nei.first + cur.first){
                disq[nei.second] = nei.first + cur.first;
                dtr.push(ii(disq[nei.second],nei.second));
            }
        }
    }

    for(int i = 0;i < n;i++){
       // cout << disq[i] << " ";
    }
    //cout << "\n";

    dis[s] = 0;
    dtr.push(ii(0,s));
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(ii nei : adj[cur.second]){
            if(dis[nei.second] > nei.first + cur.first){
                dis[nei.second] = nei.first + cur.first;
                dtr.push(ii(dis[nei.second],nei.second));
            }
        }
    }

    for(int i = 0;i < n;i++){
       // cout << dis[i] << " ";
    }
    //cout << "\n";


    dist[t] = 0;
    dtr.push(ii(0,t));
    while(!dtr.empty()){
        ii cur = dtr.top();
        dtr.pop();
        for(ii nei : adj[cur.second]){
            if(dist[nei.second] > nei.first + cur.first){
                dist[nei.second] = nei.first + cur.first;
                dtr.push(ii(dist[nei.second],nei.second));
            }
        }
    }

    for(int i = 0;i < n;i++){
        //cout << dist[i] << " ";
    }
   // cout << "\n";


    vector<int> dag[n];
    int indegree[n];
    fill(indegree,indegree+n,0);
    for(int u = 0;u < n;u++){
        if(dis[u]+dist[u] != dis[t]) continue;
        for(ii v : adj[u]){
            if(dis[v.second] + dist[v.second] != dis[t]) continue;
            if(dis[u] + v.first == dis[v.second]){
               // cout << v.second << " " << u << "\n";
                dag[v.second].push_back(u);
                indegree[u]++;
            }
        }
    }
    //cout << "\n\n";
    ii dp[n];
    for(int i = 0;i < n;i++){
        dp[i] = ii(disp[i],disq[i]);

    }
    queue<int> bfs;
    bfs.push(t);
    while(!bfs.empty()){
        int u = bfs.front();
        bfs.pop();
        //cout << u << " ";
        for(int v : dag[u]){
            indegree[v]--;
            if(indegree[v] == 0) bfs.push(v);
            dp[v].first = min(dp[v].first, dp[u].first);
            dp[v].second = min(dp[v].second, dp[u].second);
        }
    }
    long long ans = disp[q];
    //cout << "\n";
    for(int i = 0;i < n;i++){
        //cout << dp[i].first << " " << dp[i].second << "\n";
        if(dis[i]+dist[i] != dis[t]) continue;
        ans = min(ans, disq[i] + dp[i].first);
        ans = min(ans, disp[i] + dp[i].second);
    }

    cout << ans << "\n";


    return 0;
}

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