제출 #932891

#제출 시각아이디문제언어결과실행 시간메모리
932891OggyCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
156 ms68948 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll, ll> #define pii pair<int, int> #define fi first #define se second const int N = 2e6 + 7; const ll INF = 1e18; int node, edge, trace[N], par[N], s, t, n, m; vector<pll> adj[N]; queue<int> q; bool vst[N]; ll dp[N]; // void run_with_file(){ // if(fopen(file".inp", "r")){ // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); // } // } void inp(){ cin >> node >> edge; cin >> s >> t; cin >> n >> m; for(int i = 1; i <= edge; ++i){ int u, v; ll w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } } void dijkstra(int x){ vector<ll> d(node + 1, INF); d[x] = 0; priority_queue<pll, vector<pll>, greater<pll>> Q; Q.push({d[x], x}); while(!Q.empty()){ pll top = Q.top(); Q.pop(); int u = top.se; ll kc = top.fi; if(d[u] < kc) continue; for(auto it : adj[u]){ int v = it.fi; ll w = it.se; if(d[v] > kc + w){ d[v] = kc + w; trace[v] = u; Q.push({d[v], v}); } } } while(t != x){ par[t] = trace[t]; t = trace[t]; } } void bfs(int x){ vst[x] = true; q.push(x); while(!q.empty()){ int u = q.front(); q.pop(); for(auto it : adj[u]){ int v = it.fi; ll w = it.se; if(!vst[v]){ q.push(v); vst[v] = true; dp[v] = dp[u] + w * (par[v] != u ? 1 : 0); } else{ dp[v] = min(dp[v], dp[u] + w * (par[v] != u ? 1 : 0)); } } } } int main(){ cin.tie(0)->sync_with_stdio(0); // run_with_file(); inp(); dijkstra(s); bfs(n); cout << dp[m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...