제출 #659619

#제출 시각아이디문제언어결과실행 시간메모리
659619a_aguiloCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
1216 ms45388 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...