제출 #1029443

#제출 시각아이디문제언어결과실행 시간메모리
1029443ArshiaDadrasCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
231 ms76676 KiB
/* In the name of Allah */ // Welcome to the Soldier Side! // Where there's no one here, but me... #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int n, m, s1, t1, s2, t2; vector<pair<int, int>> adj[N]; long long result, d[N], du[N], dv[N], dp[N][2]; void dijkstra1(int root, long long dst[]) { priority_queue<pair<long long, int>> q; memset(dst, 63, N * sizeof(long long)); q.push({dst[root] = 0, root}); while (!q.empty()) { int u = q.top().second; q.pop(); for (auto [v, w]: adj[u]) if (dst[v] > dst[u] + w) { dst[v] = dst[u] + w; q.push({-dst[v], v}); } } } void dijkstra2(int st, int en) { priority_queue<pair<long long, int>> q; memset(dp, 63, sizeof dp); memset(d, 63, sizeof d); q.push({d[st] = 0, st}); dp[st][0] = du[st]; dp[st][1] = dv[st]; while (!q.empty()) { int u = q.top().second; q.pop(); for (auto [v, w]: adj[u]) if (d[v] > d[u] + w) { d[v] = d[u] + w; q.push({-d[v], v}); dp[v][0] = min(du[v], dp[u][0]); dp[v][1] = min(dv[v], dp[u][1]); } else if (d[v] == d[u] + w && min(du[v], dp[u][0]) + min(dv[v], dp[u][1]) <= dp[v][0] + dp[v][1]) { dp[v][0] = min(du[v], dp[u][0]); dp[v][1] = min(dv[v], dp[u][1]); } } result = min(result, dp[en][0] + dp[en][1]); } void read_input() { cin >> n >> m; cin >> s1 >> t1; cin >> s2 >> t2; s1--, t1--, s2--, t2--; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } } void solve() { dijkstra1(s2, du); dijkstra1(t2, dv); } void write_output() { result = du[t2]; dijkstra2(s1, t1); dijkstra2(t1, s1); cout << result << endl; } int main() { ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); read_input(), solve(), write_output(); return 0; }

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

commuter_pass.cpp: In function 'void dijkstra1(int, long long int*)':
commuter_pass.cpp:20:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |   for (auto [v, w]: adj[u])
      |             ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:39:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |   for (auto [v, w]: adj[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...