제출 #698947

#제출 시각아이디문제언어결과실행 시간메모리
698947RandomLBCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
318 ms39740 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef pair<ll, ll> pll; typedef pair<ll, pi> E; #define pb push_back #define siz(x) (int)x.size() #define ms(x, a) memset(x, a, sizeof(x)) #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values){ cout << vars << " = "; string delim = ""; (...,(cout << delim << values, delim = ", ")); cout << endl; } const ll LLINF = 0x3f3f3f3f3f3f3f3f; //=========================================== const int MAX = 1e5+5; vector<pll> adj[MAX]; vector<int> pp[MAX], adj2[MAX], radj[MAX]; ll dis[MAX], dis2[4][MAX]; bool vis[MAX]; int main(){ cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; int s, t, src, tar; cin >> s >> t >> src >> tar; for (int i = 1; i <= m; i++){ int a, b, w; cin >> a >> b >> w; adj[a].pb({b, w}); adj[b].pb({a, w}); } ms(dis, 0x3f3f3f3f); ms(dis2, 0x3f3f3f3f); priority_queue<pll, vector<pll>, greater<pll>> pq; pq.push({dis[s] = 0, s}); while (siz(pq)){ auto[d, v] = pq.top(); pq.pop(); if (d != dis[v]) continue; for (auto[u, w]: adj[v]){ if (dis[u] > dis[v]+w){ pq.push({dis[u] = dis[v]+w, u}); pp[u] = {v}; } else if (dis[u] == dis[v]+w) pp[u].pb(v); } } //for (int i = 1; i <= n; i++) deb(i, dis[i]); queue<int> q; vis[t] = true; q.push(t); while (siz(q)){ int v = q.front(); q.pop(); for (int u: pp[v]){ adj2[v].pb(u); radj[u].pb(v); if (!vis[u]){ vis[u] = true; q.push(u); } } } priority_queue<E, vector<E>, greater<E>> q2; q2.push({dis2[0][src] = 0, {0, src}}); while (siz(q2)){ auto[d, x] = q2.top(); q2.pop(); auto[i, v] = x; if (v == tar){ cout << d << "\n"; return 0; } if (d != dis2[i][v]) continue; for (auto[u, w]: adj[v]){ int ni = (!i? 0 : 3); if (dis2[ni][u] > dis2[i][v]+w){ q2.push({dis2[ni][u] = dis2[i][v]+w, {ni, u}}); } } if (!i || i == 1){ for (int u: adj2[v]){ if (dis2[1][u] > dis2[i][v]){ q2.push({dis2[1][u] = dis2[i][v], {1, u}}); } } } if (!i || i == 2){ for (int u: radj[v]){ if (dis2[2][u] > dis2[i][v]){ q2.push({dis2[2][u] = dis2[i][v], {2, u}}); } } } } }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:46:26: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   46 |                 pp[u] = {v};
      |                          ^
commuter_pass.cpp:46:26: warning: narrowing conversion of 'v' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...