제출 #944061

#제출 시각아이디문제언어결과실행 시간메모리
944061tnknguyen_Commuter Pass (JOI18_commuter_pass)C++14
16 / 100
217 ms21192 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define pll pair<long long, long long> const int sz = 1e5 + 5; vector<pll> gr[sz]; long long n, m, S, T, U, V; long long d[5][sz]; int vi[sz], viid = 0; //constants long long INF; long long ST; void Dijkstra(int s, int k){ priority_queue<pll> q; d[k][s] = 0; q.push({0, s}); while(q.size()){ long long w, u; tie(w, u) = q.top(); w = -w; q.pop(); if(w > d[k][u]){ continue; } for(pll p : gr[u]){ long long v, c; tie(v, c) = p; if(w + c < d[k][v]){ d[k][v] = w + c; q.push({-d[k][v], v}); } } } } namespace SUB1{ bool ok(){ return (S == U); } void solve(){ Dijkstra(V, 3); long long ans = 1e18; for(int i=1;i<=n;++i){ if(d[0][i] + d[1][i] == d[0][T]){ ans = min(ans, d[3][i]); } } cout<<ans; //-------------------- exit(0); } } long long dist[305][305]; namespace SUB2{ // n <= 300 bool ok(){ return (n <= 300); } void solve(){ memset(dist, 0x3f, sizeof(dist)); for(int i=1;i<=n;++i){ dist[i][i] = 0; for(pll p : gr[i]){ long long v, c; tie(v, c) = p; dist[i][v] = c; } } // Floyd - Warshall vector<pll> nodes; for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); if(d[0][i] + d[1][j] == ST){ nodes.push_back({i, j}); } } } } Dijkstra(U, 3); Dijkstra(V, 4); long long ans = 1e18; for(pll p : nodes){ int i, j; tie(i, j) = p; //U -> i ---> j -> V; ans = min(ans, d[3][i] + d[4][j]); //U -> j ---> i -> V; ans = min(ans, d[4][i] + d[3][j]); } cout<<ans; //---------------------- exit(0); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("PATHLIB.inp","r",stdin); //freopen("PATHLIB.out","w",stdout); cin >> n >> m; cin >> S >> T; cin >> U >> V; for(int i=1;i<=m;++i){ int u, v, c; cin>>u>>v>>c; gr[u].push_back({v, c}); gr[v].push_back({u, c}); } memset(d, 0x3f, sizeof(d)); INF = d[0][0]; Dijkstra(S, 0); Dijkstra(T, 1); ST = d[0][T]; if(SUB1::ok()){ //S == U SUB1::solve(); } if(SUB2::ok()){ //n <= 300 SUB2::solve(); } 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...