oj.uz

답안 #659619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659619 2022-11-18T18:55:20 Z a_aguilo Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 1216 ms 45388 KB 
#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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 474 ms 34908 KB Output is correct
2 Correct 470 ms 36340 KB Output is correct
3 Correct 514 ms 45292 KB Output is correct
4 Correct 477 ms 38664 KB Output is correct
5 Correct 468 ms 41056 KB Output is correct
6 Correct 469 ms 38728 KB Output is correct
7 Correct 635 ms 41728 KB Output is correct
8 Correct 574 ms 41420 KB Output is correct
9 Correct 452 ms 39608 KB Output is correct
10 Correct 433 ms 39288 KB Output is correct
11 Correct 203 ms 30576 KB Output is correct
12 Correct 438 ms 39168 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 464 ms 37304 KB Output is correct
2 Correct 432 ms 37724 KB Output is correct
3 Correct 430 ms 37072 KB Output is correct
4 Correct 442 ms 37628 KB Output is correct
5 Correct 449 ms 38280 KB Output is correct
6 Correct 483 ms 40856 KB Output is correct
7 Correct 481 ms 41552 KB Output is correct
8 Correct 448 ms 37948 KB Output is correct
9 Correct 484 ms 38392 KB Output is correct
10 Correct 437 ms 37156 KB Output is correct
11 Correct 245 ms 30852 KB Output is correct
12 Correct 492 ms 41404 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 3396 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 60 ms 7036 KB Output is correct
5 Correct 30 ms 3940 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 3 ms 448 KB Output is correct
10 Correct 29 ms 4000 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 474 ms 34908 KB Output is correct
2 Correct 470 ms 36340 KB Output is correct
3 Correct 514 ms 45292 KB Output is correct
4 Correct 477 ms 38664 KB Output is correct
5 Correct 468 ms 41056 KB Output is correct
6 Correct 469 ms 38728 KB Output is correct
7 Correct 635 ms 41728 KB Output is correct
8 Correct 574 ms 41420 KB Output is correct
9 Correct 452 ms 39608 KB Output is correct
10 Correct 433 ms 39288 KB Output is correct
11 Correct 203 ms 30576 KB Output is correct
12 Correct 438 ms 39168 KB Output is correct
13 Correct 464 ms 37304 KB Output is correct
14 Correct 432 ms 37724 KB Output is correct
15 Correct 430 ms 37072 KB Output is correct
16 Correct 442 ms 37628 KB Output is correct
17 Correct 449 ms 38280 KB Output is correct
18 Correct 483 ms 40856 KB Output is correct
19 Correct 481 ms 41552 KB Output is correct
20 Correct 448 ms 37948 KB Output is correct
21 Correct 484 ms 38392 KB Output is correct
22 Correct 437 ms 37156 KB Output is correct
23 Correct 245 ms 30852 KB Output is correct
24 Correct 492 ms 41404 KB Output is correct
25 Correct 30 ms 3396 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 60 ms 7036 KB Output is correct
29 Correct 30 ms 3940 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 4 ms 596 KB Output is correct
32 Correct 6 ms 724 KB Output is correct
33 Correct 3 ms 448 KB Output is correct
34 Correct 29 ms 4000 KB Output is correct
35 Correct 1 ms 304 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 2 ms 468 KB Output is correct
40 Correct 428 ms 38248 KB Output is correct
41 Correct 446 ms 39200 KB Output is correct
42 Correct 445 ms 39268 KB Output is correct
43 Correct 258 ms 34760 KB Output is correct
44 Correct 245 ms 34732 KB Output is correct
45 Correct 1125 ms 45388 KB Output is correct
46 Correct 1216 ms 44956 KB Output is correct
47 Correct 429 ms 38648 KB Output is correct
48 Correct 253 ms 32992 KB Output is correct
49 Correct 422 ms 37860 KB Output is correct
50 Correct 888 ms 43424 KB Output is correct
51 Correct 558 ms 44944 KB Output is correct