제출 #930049

#제출 시각아이디문제언어결과실행 시간메모리
930049jcelinCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
686 ms103508 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<pll> vpll; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; //998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int MAXN = 1e6 + 7; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; ll dis[MAXN][4]; int n; vii g[MAXN]; vi dag[MAXN], rv[MAXN], topo; int indeg[MAXN]; bool ing[MAXN]; void dijkstra(int root, int id){ for(int i=1; i<=n; i++) dis[i][id] = INF; dis[root][id] = 0; set<pll> s; for(int i=1; i<=n; i++) s.insert({dis[i][id], i}); while(!s.empty()){ ll d, u; tie(d, u) = *s.begin(); s.erase(s.begin()); for(auto &x : g[u]){ int v = x.X; ll nd = d + x.Y; if(nd < dis[v][id]){ s.erase({dis[v][id], v}); dis[v][id] = nd; s.insert({dis[v][id], v}); } } } } ll dp[MAXN], dp2[MAXN]; void solve(){ int m; int s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i=0; i<m; i++){ int a, b, w; cin >> a >> b >> w; g[a].PB({b, w}); g[b].PB({a, w}); } dijkstra(s, 0); dijkstra(t, 1); dijkstra(u, 2); dijkstra(v, 3); ll opt = INF, ans = INF; for(int i=1; i<=n; i++) opt = min(opt, dis[i][0] + dis[i][1]), ans = min(ans, dis[i][2] + dis[i][3]); for(int i=1; i<=n; i++) ing[i] = (dis[i][0] + dis[i][1] == opt); for(int i=1; i<=n; i++){ for(auto &x : g[i]){ if(dis[i][0] + x.Y + dis[x.X][1] == opt){ dag[i].PB(x.X); rv[x.X].PB(i); indeg[x.X]++; } } } vi st; for(int i=1; i<=n; i++){ if(!ing[i]) continue; if(indeg[i] == 0) st.PB(i); } while(st.size()){ int cr = st.back(); st.PPB(); topo.PB(cr); for(auto &x : dag[cr]) if(--indeg[x] == 0) st.PB(x); } for(int i=1; i<=n; i++) dp[i] = dis[i][2], dp2[i] = dis[i][3]; for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]); reverse(all(topo)); for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]); reverse(all(topo)); for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]); for(int i=1; i<=n; i++) dp[i] = dis[i][3], dp2[i] = dis[i][2]; for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]); reverse(all(topo)); for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]); reverse(all(topo)); for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]); cout << ans << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; while(t--) 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...