제출 #944149

#제출 시각아이디문제언어결과실행 시간메모리
944149tnknguyen_Commuter Pass (JOI18_commuter_pass)C++14
40 / 100
270 ms29444 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 dp[5][sz]; long long d[5][sz]; //constants long long INF; long long ST; // ------------- FUNCTIONS ------------- // 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}); } } } } vector<int> dag[sz]; int vi[sz]; void build_DAG(int v){ // vi[v] = 1; // for(pll p : gr[v]){ // long long u, c; // tie(u, c) = p; // if(d[0][u] + c + d[1][v] == ST){ // dag[u].push_back(v); // if(vi[u] == 0){ // build_DAG(u); // } // } // } vector<long long> d_dag(n + 5, INF); priority_queue<pll> q; q.push({0, S}); d_dag[S] = 0; while(q.size()){ long long w, u; tie(w, u) = q.top(); w = -w; q.pop(); if(w > d_dag[u]){ continue; } for(pll p : gr[u]){ long long v, c; tie(v, c) = p; if(w + c < d_dag[v]){ d_dag[v] = w + c; q.push({-d_dag[v], v}); dag[u].clear(); dag[v].push_back(u); } else if(w + c == d_dag[v]){ dag[v].push_back(u); } } } } void topo(int u){ vi[u] = 2; for(int v : dag[u]){ dp[1][u] = min(dp[1][u], dp[1][v]); dp[2][u] = min(dp[2][u], dp[2][v]); if(vi[v] != 2){ topo(v); } } priority_queue<pll> q; } // ------------- SUBTASK ------------- // 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 ds2[305][305]; namespace SUB2{ // n <= 300 bool ok(){ return (n <= 300); } void solve(){ memset(ds2, 63, sizeof(ds2)); for(int i=1;i<=n;++i){ ds2[i][i] = 0; for(pll p : gr[i]){ ds2[i][p.first] = p.second; } } // Floyd - Warshall for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ ds2[i][j] = min(ds2[i][j], ds2[i][k] + ds2[k][j]); } } } long long ans = ds2[U][V]; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(ds2[S][i] + ds2[i][j] + ds2[j][T] == ST){ ans = min(ans, ds2[U][i] + ds2[j][V]); ans = min(ans, ds2[U][j] + ds2[i][V]); } } } cout<<ans; //---------------------- exit(0); } } namespace SUB3{ void solve(){ build_DAG(T); Dijkstra(U, 3); Dijkstra(V, 4); memset(dp, 63, sizeof(dp)); for(int i=1;i<=n;++i){ dp[1][i] = d[3][i]; dp[2][i] = d[4][i]; } // topo(S); long long ans = d[3][V]; priority_queue<pll> q; vector<long long> ds3(n+5, INF); ds3[T] = d[3][T]; ds3 = vector<long long>(n + 5, INF); ds3[T] = d[4][T]; while(q.size()){ long long w, u; tie(w, u) = q.top(); w = -w; q.pop(); if(w > ds3[u]){ continue; } ans = min(ans, w + d[4][u]); for(int v : dag[u]){ long long c = min(w, d[4][u]); if(c < ds3[v]){ ds3[v] = c; q.push({-c, v}); } } } ds3 = vector<long long>(n + 5, INF); ds3[T] = d[4][T]; while(q.size()){ long long w, u; tie(w, u) = q.top(); w = -w; q.pop(); if(w > ds3[u]){ continue; } ans = min(ans, w + d[3][u]); for(int v : dag[u]){ long long c = min(w, d[3][u]); if(c < ds3[v]){ ds3[v] = c; q.push({-c, v}); } } } // for(int i=1;i<=n;++i){ // ans = min({ans, dp[1][i] + d[4][i], dp[2][i] + d[3][i]}); // } cout<<ans; } } 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, 63, 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(); } SUB3::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...