제출 #301298

#제출 시각아이디문제언어결과실행 시간메모리
301298pit4hCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
342 ms19128 KiB
#include<bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #ifndef LOCAL #define cerr if(0)cerr #endif using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using vi = vector<int>; const ll INF = 1e16+1; void dijkstra(int s, vector<vector<pii>>& g, vector<ll>& d) { int n = g.size()-1; vector<bool> vis(n+1); priority_queue<pair<ll, int>> Q; d[s] = 0; Q.push({d[s], s}); while(Q.size()) { int cur = Q.top().nd; Q.pop(); if(vis[cur]) continue; vis[cur] = 1; for(auto nxt: g[cur]) { if(!vis[nxt.st] && d[nxt.st] > d[cur] + nxt.nd) { d[nxt.st] = d[cur] + nxt.nd; Q.push({-d[nxt.st], nxt.st}); } } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n, m; cin>>n>>m; int s, t; cin>>s>>t; int u, v; cin>>u>>v; vector<vector<pii>> g(n+1); for(int i=0; i<m; ++i) { int a, b, c; cin>>a>>b>>c; g[a].push_back({b, c}); g[b].push_back({a, c}); } vector<ll> d_s(n+1, INF), d_t(n+1, INF); dijkstra(s, g, d_s); dijkstra(t, g, d_t); for(int i=1; i<=n; ++i) { for(auto& edge: g[i]) { int j = edge.st, w = edge.nd; if(d_s[i] + w + d_t[j] == d_s[t]) { edge.nd = 0; } } } vector<ll> d(n+1, INF); dijkstra(u, g, d); vector<ll> D(n+1, INF); dijkstra(v, g, D); cout<<min(d[v], D[u]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...