Submission #1216087

#TimeUsernameProblemLanguageResultExecution timeMemory
1216087kiennguyendinhCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
2095 ms20392 KiB
#include <bits/stdc++.h> using namespace std; int n,m,S,T,U,V,x,y; long long w; vector<pair<int,pair<long long,int>>> adj[100001]; bool c[200001]; long long dist[2][100001]; int pre[2][100001]; void dik(int t,int sta){ for(int i = 1;i <= n;i++) dist[t][i] = LLONG_MAX; dist[t][sta] = 0; queue<int> q; q.push(sta); while(!q.empty()){ int u = q.front(); q.pop(); for(pair<int,pair<long long,int>> &v : adj[u]){ if(c[v.second.second]){ if(dist[t][v.first] > dist[t][u]){ dist[t][v.first] = dist[t][u]; pre[t][v.first] = u; q.push(v.first); } continue; } if(dist[t][v.first] > dist[t][u] + v.second.first){ dist[t][v.first] = dist[t][u] + v.second.first; q.push(v.first); pre[t][v.first] = u; } } } } long long res = LLONG_MAX; void track(int t,int sta,int en){ while(sta != en){ //cout << sta << " - {"; int u = pre[t][sta]; long long d = dist[t][sta] - dist[t][u]; for(pair<int,pair<long long,int>> &v : adj[u]){ if(v.first == sta && d == v.second.first){ c[v.second.second] = true; break; } } //cout << d << "} - "; sta = u; } //cout << en << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n >> m >> S >> T >> U >> V; for(int i = 1;i <= m;i++){ cin >> x >> y >> w; adj[x].push_back({y,{w,i}}); adj[y].push_back({x,{w,i}}); } dik(0,S); track(0,T,S); dik(1,U); track(1,V,U); res = dist[1][V]; //for(int i = 1;i <= m;i++) c[i] = false; //dik(1,U); //track(1,V,U); //dik(0,S); //res = min(res,dist[0][T]); cout << res; 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...