제출 #208814

#제출 시각아이디문제언어결과실행 시간메모리
208814SiberianCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
2097 ms18772 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; #define all(x) x.begin(), x.end() template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;} template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;} #define int ll struct edge{ int to, cost; edge() {} edge(int _to, int _cost) { to = _to, cost = _cost; } }; const int MAXN = 1e5 + 10; vector<edge> g[MAXN]; int n, m; int s1, t1; int s2, t2; void read() { cin >> n >> m; cin >> s1 >> t1; s1--; t1--; cin >> s2 >> t2; s2--; t2--; for (int i = 0; i < m; i++) { int u, v; int c; cin >> u >> v >> c; u--; v--; g[u].push_back({v, c}); g[v].push_back({u, c}); } } const ll INF = 1e18; ll ans; vector<ll> djkstra(int v) { vector<ll> d(n, INF); set<pair<ll, int>> q; d[v] = 0; q.insert({0, v}); while (!q.empty()) { int v = q.begin()->second; //cout << v << " " << d[v] << endl; q.erase(q.begin()); for (auto [to, cost] : g[v]) { if (d[to] <= d[v] + cost) continue; q.erase({d[to], to}); d[to] = d[v] + cost; q.insert({d[to], to}); } } return d; } vector<ll> dist; void build() { auto d = djkstra(s1); /*cout << "d = " << endl; for (auto i : d) { cout << i << " "; } cout << endl;*/ //exit(0); dist.assign(n, INF); queue<int> q; q.push(t1); dist[t1] = d[t1]; while (!q.empty()) { int v = q.front(); q.pop(); for (auto [to, cost] : g[v]) { if (dist[to] != INF) continue; if (d[to] + cost != d[v]) continue; dist[to] = d[to]; q.push(to); } } } vector<ll> dp; vector<bool> used; ll dfs(int v) { if (used[v]) return dp[v]; used[v] = true; for (auto [to, cost] : g[v]) { if (dist[v] + cost != dist[to]) continue; chkmin(dp[v], dfs(to)); } return dp[v]; } bool check(int v, int need) { if (v == need) return true; for (auto [to, cost] : g[v]) { if (dist[to] != dist[v] + cost) continue; if (check(to, need)) return true; } return false; } void run() { build(); /*cout << "dist = " << endl; for (auto i : dist) { cout << i << " "; } cout << endl;*/ //dp = djkstra(t2); //used.assign(n, false); //dfs(s1); vector<ll> S = djkstra(s2); vector<ll> T = djkstra(t2); ans = S[t2]; for (int i = 0; i < n; i++) { if (dist[i] == INF) continue; for (int j = 0; j < n; j++) { if (dist[j] == INF) continue; if (!check(i, j)) continue; chkmin(ans, S[i] + T[j]); } } //ans = have[t2]; //for (int i = 0; i < n; i++) { // if (dist[i] == INF) continue; // chkmin(ans, dp[i] + have[i]); //} } void write() { cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); read(); run(); write(); return 0; }

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

commuter_pass.cpp: In function 'std::vector<long long int> djkstra(ll)':
commuter_pass.cpp:57:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [to, cost] : g[v]) {
             ^
commuter_pass.cpp: In function 'void build()':
commuter_pass.cpp:84:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [to, cost] : g[v]) {
             ^
commuter_pass.cpp: In function 'll dfs(ll)':
commuter_pass.cpp:99:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, cost] : g[v]) {
            ^
commuter_pass.cpp: In function 'bool check(ll, ll)':
commuter_pass.cpp:108:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [to, cost] : g[v]) {
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...