Submission #983072

#TimeUsernameProblemLanguageResultExecution timeMemory
983072faricaCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
214 ms25872 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MAX_N = 100000; int n, s, t, u, v, D[MAX_N][2]; vector<vector<int>>parent(MAX_N); vector<pair<int,int>>dp(MAX_N), M(MAX_N); vector<vector<pair<int,int>>>adjL(MAX_N); void calc(int x, int type) { priority_queue<pair<int,int>>pq; pq.push({0, x}); for(int i=0; i<n; ++i) D[i][type] = -1; D[x][type] = 0; while(!pq.empty()) { int cur = pq.top().second; pq.pop(); for(pair<int,int>adj: adjL[cur]) { int w = adj.second + D[cur][type]; if(D[adj.first][type] == -1) { D[adj.first][type] = w; pq.push({-w, adj.first}); } } } } pair<int,int> func(int pos) { if(dp[pos].first != -1) return dp[pos]; dp[pos].first = M[pos].first = D[pos][0]; dp[pos].second = M[pos].second = D[pos][1]; M[pos].second = D[pos][1]; for(int p: parent[pos]) { pair<int,int>cnt = func(p); M[pos].first = min(M[pos].first, M[p].first); M[pos].second = min(M[pos].second, M[p].second); if(cnt.first + cnt.second < dp[pos].first + dp[pos].second) dp[pos].first = cnt.first, dp[pos].second = cnt.second; } int X = M[pos].first + D[pos][1], Y = M[pos].second + D[pos][0]; if(X < Y && X < dp[pos].first + dp[pos].second) dp[pos].first = M[pos].first, dp[pos].second = D[pos][1]; else if(Y < dp[pos].first + dp[pos].second) dp[pos].second = M[pos].second, dp[pos].first = D[pos][0]; return {0, M[pos].second}; } void solve() { int m; cin >> n >> m >> s >> t >> u >> v; --s, --t, --u, --v; for(int i=0; i<m; ++i) { int a, b, w; cin >> a >> b >> w; --a, --b; adjL[a].push_back({b, w}); adjL[b].push_back({a, w}); } for(int i=0; i<n; ++i) dp[i] = {-1, -1}; priority_queue<pair<int,int>>pq; pq.push({0, s}); vector<int>d(n, -1); d[s] = 0; while(!pq.empty()) { int dist = -pq.top().first, cur = pq.top().second; pq.pop(); for(pair<int,int>adj: adjL[cur]) { int w = dist + adj.second; if(d[adj.first] == -1) { pq.push({-w, adj.first}); d[adj.first] = w; parent[adj.first].push_back(cur); } else if(w == d[adj.first]) parent[adj.first].push_back(cur); } } calc(u, 0); calc(v, 1); func(t); cout << min(dp[t].first + dp[t].second, min(D[u][1], D[v][0])) << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("shortcut.in", "r", stdin); //freopen("shortcut.out", "w", stdout); int t=1; 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...