제출 #1082755

#제출 시각아이디문제언어결과실행 시간메모리
1082755khoile25108Commuter Pass (JOI18_commuter_pass)C++14
15 / 100
2057 ms21644 KiB
#include <bits/stdc++.h> using namespace std; #define faster ios_base::sync_with_stdio(0); cin.tie(0); #define FOR(i,a,b) for(int i = a; i <= b; i++) #define FOD(i,a,b) for(int i = a; i >= b; i--) #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define lcm(a,b) (a*b)/__gcd(a,b) #define ii pair<int,int> #define iii pair<int,pair<int,int>> #define iv pair<pair<int,int>,pair<int,int>> const int inf = 1e9; const ll INF = 1e18; const int mod = 1e9 + 7; const int N = 1e5 + 105; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const int dxx[] = {-1,-1,0,1,1,1,0,-1}; const int dyy[] = {0,1,1,1,0,-1,-1,-1}; int n, m, s, t, x, y; ll ans; vector<ii> g[N]; ll d[3][N], best[2][N]; void dijk(int type, int beg) { priority_queue<ii,vector<ii>,greater<ii>> pq; FOR(i,1,n) d[type][i] = INF; d[type][beg] = 0; pq.push({0,beg}); while(!pq.empty()) { int u = pq.top().se; int cost = pq.top().fi; pq.pop(); if(cost > d[type][u]) continue; for(ii h : g[u]) { int v = h.fi; int l = h.se; if(d[type][v] > d[type][u] + l) { d[type][v] = d[type][u] + l; pq.push({d[type][v], v}); } } } } void dfs(int u) { best[0][u] = d[1][u]; best[1][u] = d[2][u]; for(ii h : g[u]) { int v = h.fi; if(d[0][v] + h.se == d[0][u]) { dfs(v); best[0][u] = min(best[0][u], best[0][v]); best[1][u] = min(best[1][u], best[1][v]); } } ans = min(ans, d[1][u] + best[1][u]); ans = min(ans, d[2][u] + best[0][u]); } void solve() { dijk(0,s); dijk(1,x); dijk(2,y); ans = d[1][y]; dfs(t); cout << ans; } void input() { //freopen("BUS.INP", "r", stdin); //freopen("BUS.OUT", "w", stdout); cin >> n >> m >> s >> t >> x >> y; FOR(i,1,m) { int u, v, w; cin >> u >> v >> w; g[u].pb({v,w}); g[v].pb({u,w}); } } signed main() { faster input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...