Submission #659619

#	Time	Username	Problem	Language	Result	Execution time	Memory
659619		a_aguilo	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1216 ms	45388 KiB

commuter_pass

#include<bits/stdc++.h>
#define int long long

using namespace std;

int N, M, S, T, U, V;
vector<long long> DistancesFromS, DistancesFromT, DistancesFromU, DistancesFromV, DPfromUDAG1, DPfromUDAG2, DPfromVDAG1, DPfromVDAG2;
vector<vector<int>> edges, DAG1, DAG2;
vector<vector<pair<int, int>>> AdjList;

void Dijkstra(int start, vector<long long>& distances){
    priority_queue<pair<long long, int>> PQ;
    PQ.push({-0, start});
    while(!PQ.empty()){
        pair<int, int> act = PQ.top(); PQ.pop();
        int NodeAct = act.second;
        long long DistAct = -1*act.first;
        if(distances[NodeAct] != -1) continue;
        distances[NodeAct] = DistAct;
        for(pair<int, int> next : AdjList[NodeAct]){
            int neighbour = next.first;
            long long cost = (long long)next.second;
            if(distances[neighbour] == -1)PQ.push({-((long long)DistAct+cost), neighbour});
        }
    }
}
void fillDPDAG1WithU(int node){
    //cout << "nodo " << node << " DP from U in DAG1 " << DPfromUDAG1[node] << endl;
    //cout << "nodo " << node << " DP from V in DAG1 " << DPfromVDAG1[node] << endl;
    for(int son: DAG1[node]){
        long long proposal = min(DPfromUDAG1[node], DistancesFromU[son]);
        if(DPfromUDAG1[son] <= proposal) continue;
        DPfromUDAG1[son] = proposal;
        fillDPDAG1WithU(son);
    }
}

void fillDPDAG1WithV(int node){
    //cout << "nodo " << node << " DP from U in DAG1 " << DPfromUDAG1[node] << endl;
    //cout << "nodo " << node << " DP from V in DAG1 " << DPfromVDAG1[node] << endl;
    for(int son: DAG1[node]){
        long long proposal = min(DPfromVDAG1[node], DistancesFromV[son]);
        if(DPfromVDAG1[son] <= proposal) continue;
        DPfromVDAG1[son] = proposal;
        fillDPDAG1WithV(son);
    }
}

void fillDPDAG2WithU(int node){
    for(int son: DAG2[node]){
        long long proposal = min(DPfromUDAG2[node], DistancesFromU[son]);
        if(DPfromUDAG2[son] <= proposal) continue;
        DPfromUDAG2[son] = proposal;
        fillDPDAG2WithU(son);
    }
}
void fillDPDAG2WithV(int node){
    for(int son: DAG2[node]){
        long long proposal = min(DPfromVDAG2[node], DistancesFromV[son]);
        if(DPfromVDAG2[son] <= proposal) continue;
        DPfromVDAG2[son] = proposal;
        fillDPDAG2WithV(son);
    }
}
signed main(){
    cin >> N >> M >> S >> T >> U >> V;
    S--; T--; U--; V--;
    int a, b, c;
    edges = vector<vector<int>> (M, vector<int>(3));
    AdjList = vector<vector<pair<int, int>>> (N);
    for(int i = 0; i < M; ++i){
        cin >> a >> b >> c; a--; b--;
        AdjList[a].push_back({b, c});
        AdjList[b].push_back({a, c});
        edges[i][0] = a;
        edges[i][1] = b;
        edges[i][2] = c;
    }
    DistancesFromS = vector<long long>(N, -1); 
    DistancesFromT = vector<long long>(N, -1); 
    DistancesFromU = vector<long long>(N, -1); 
    DistancesFromV = vector<long long>(N, -1); 
    //cout << "First i/o ok" << endl;
    Dijkstra(S, DistancesFromS);
    Dijkstra(T, DistancesFromT);
    Dijkstra(U, DistancesFromU);
    Dijkstra(V, DistancesFromV);
    //cout << "Dijkstras ok" << endl;
    DAG1 = vector<vector<int>> (N);//DAG1 de S a T
    DAG2 = vector<vector<int>> (N);//DAG2 de T a S
    int minCost = DistancesFromS[T];
    vector<bool> AreInDAG(N, false);
    for(vector<int> edge: edges){
        //cout << edge[0] << " " << edge[1] << " " << edge[2] << endl;
        if((DistancesFromS[edge[0]] + DistancesFromT[edge[1]] + edge[2]) == minCost){
            //uso de a->b para ir de S a T
            DAG1[edge[0]].push_back(edge[1]);
            DAG2[edge[1]].push_back(edge[0]);
            AreInDAG[edge[0]] = true;
            AreInDAG[edge[1]] = true;
            //cout << "edge in DAG1 from " << edge[0] << " to " << edge[1] << endl;
            //cout << "edge in DAG2 from " << edge[1] << " to " << edge[0] << endl;
        }
        else if((DistancesFromT[edge[0]] + DistancesFromS[edge[1]] + edge[2]) == minCost){
            //uso de b->a para ir de S a T
            DAG1[edge[1]].push_back(edge[0]);
            DAG2[edge[0]].push_back(edge[1]);
            AreInDAG[edge[0]] = true;
            AreInDAG[edge[1]] = true;
            //cout << "edge in DAG1 from " << edge[1] << " to " << edge[0] << endl;
            //cout << "edge in DAG2 from " << edge[0] << " to " << edge[1] << endl;
        }
    }
  	DPfromUDAG1 = vector<long long>(N, 1e17);
    DPfromUDAG1[S] = DistancesFromU[S];
    DPfromUDAG2 = vector<long long>(N, 1e17);
    DPfromUDAG2[T] = DistancesFromU[T];
    DPfromVDAG1 = vector<long long>(N, 1e17);
    DPfromVDAG1[S] = DistancesFromV[S];
    DPfromVDAG2 = vector<long long>(N, 1e17);
    DPfromVDAG2[T] = DistancesFromV[T];
    fillDPDAG1WithU(S);
    fillDPDAG1WithV(S);
    //cout << "First dp ok" << endl;
    fillDPDAG2WithU(T);
    fillDPDAG2WithV(T);
    //cout << "Second dp ok" << endl;
    /*
    for(int i = 1; i <= N; ++i){
        cout << "node " << i << " dist from U " << DistancesFromU[i-1] << " dist from V " << DistancesFromV[i-1] << endl;
    }*/
    long long ans = DistancesFromU[V];
    //cout << ans << endl;
    for(int node = 0; node < N; ++node){
        if(AreInDAG[node]) {
            ans = min(ans, min(DPfromVDAG2[node]+DPfromUDAG1[node], DPfromVDAG1[node]+DPfromUDAG2[node]));
            //cout << ans << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

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