제출 #1008946

#제출 시각아이디문제언어결과실행 시간메모리
1008946christinelynnCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
707 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(NULL); #define fi first #define se second const ll MOD = 998244353; const ll INF = 1e18; ll n, m, s, t, u, v; vector<pair<ll, ll>> adj[100005]; bool vis[100005], vis2[100005]; int main(){ //hitaf cin >> n >> m; cin >> s >> t; cin >> u >> v; vector<ll> dist(n + 2, INF), dist2(n + 2, INF); for(int i = 1; i <= m; i++){ ll x, y, w; cin >> x >> y >> w; adj[x].push_back({y, w}); adj[y].push_back({x,w}); } priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, s}); dist[s] = 0; while(!pq.empty()){ auto now = pq.top(); pq.pop(); if(dist[now.se] < now.fi) continue; for(auto v: adj[now.se]){ if(dist[v.fi] < now.fi + v.se) continue; dist[v.fi] = now.fi + v.se; pq.push({dist[v.fi], v.fi}); } } ll cur = t; vis[t] = true; while(cur != s){ for(auto v: adj[cur]){ if(dist[v.fi] + v.se == dist[cur]){ vis[v.fi] = true; cur = v.fi; break; } } } priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq2; pq2.push({0, u}); dist2[u] = 0; while(!pq2.empty()){ auto now = pq2.top(); pq2.pop(); if(dist2[now.se] < now.fi || vis2[now.se]) continue; vis2[now.se] = true; for(auto x: adj[now.se]){ if(dist2[x.fi] < now.fi + (vis[now.se] && vis[x.fi] ? 0 : x.se)) continue; dist2[x.fi] = now.fi + (vis[now.se] && vis[x.fi] ? 0 : x.se); pq2.push({dist2[x.fi], x.fi}); } } cout << dist2[v] << endl; } /* 7 1 2 9 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...