제출 #857577

#제출 시각아이디문제언어결과실행 시간메모리
857577dio_2Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
137 ms13732 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long)1e18; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; vector<vector<pair<int, int>>> adj(n + 1); while(m--){ int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } auto Do = [&](int src, vector<long long> &d)->void{ fill(d.begin(), d.end(), inf); vector<bool> in_Q(n + 1); d[src] = 0; priority_queue<pair<long long, int>> pq; pq.push({0, src}); while(!pq.empty()){ auto [_, node] = pq.top(); pq.pop(); if(in_Q[node]) continue; in_Q[node] = 1; for(auto [to, cost] : adj[node]){ if(d[node] + cost < d[to]){ d[to] = d[node] + cost; pq.push({-d[to], to}); } } } }; vector<long long> D1(n + 1); Do(s, D1); int cr = t; bool unique = 1; while(cr != s){ // making the edges in the SP free. int cnt = 0; for(auto &[node, cost] : adj[cr]){ if(D1[node] + cost == D1[cr]){ cost = 0; for(auto &[node2, cost2] : adj[node]){ if(node2 == cr){ cost2 = 0; } } cr = node; ++cnt; unique &= (cnt == 1); } } } if(unique){ vector<long long> Du(n + 1); Do(u, Du); cout << Du[v] << '\n'; return 0; } 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...