제출 #42295

#제출 시각아이디문제언어결과실행 시간메모리
42295RezwanArefin01Commuter Pass (JOI18_commuter_pass)C++14
15 / 100
2051 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> ii; const int maxn = 1e5 + 10; vector<int> adj[maxn], cost[maxn]; vector<ll> du, dv, dt, ds, dp1, dp2; void dijkstra(int s, int n, vector<ll> &d) { for(int i = 0; i < n; i++) d[i] = 1e18; priority_queue<ii, vector<ii>, greater<ii> > q; q.push({d[s] = 0, s}); while(!q.empty()) { ii x = q.top(); q.pop(); int u = x.second; ll c = x.first; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; ll w = cost[u][i]; if(d[v] > c + w) { d[v] = c + w; q.push({d[v], v}); } } } } void compute(int s, int n, vector<ll> &dp) { dp.resize(n + 1); vector<ll> d(n + 1); for(int i = 1; i <= n; i++) { dp[i] = du[i]; d[i] = 1e18; } priority_queue<ii, vector<ii>, greater<ii> > q; q.push({d[s] = 0, s}); while(!q.empty()) { ii x = q.top(); q.pop(); int u = x.second; ll c = x.first; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; ll w = cost[u][i]; if(d[v] == c + w) { // cout << u << " -> " << v << " "; d[v] = c + w; dp[v] = min(dp[v], dp[u]); q.push({d[v], v}); // cout << dp[u] << " " << dp[v] << endl; } else if(d[v] > c + w) { // cout << u << " -> " << v << " " ; d[v] = c + w; dp[v] = min(du[v], dp[u]); q.push({d[v], v}); // cout << dp[u] << " " << dp[v] << endl; } } } } int main(int argc, char const *argv[]) { int n, m, u, v, s, t; scanf("%d %d", &n, &m); scanf("%d %d", &s, &t); scanf("%d %d", &u, &v); for(int i = 0; i < m; i++) { int u, v, c; scanf("%d %d %d", &u, &v, &c); adj[u].push_back(v); adj[v].push_back(u); cost[u].push_back(c); cost[v].push_back(c); } du.resize(n + 1); dv.resize(n + 1); ds.resize(n + 1); dt.resize(n + 1); dijkstra(u, n + 1, du); dijkstra(v, n + 1, dv); dijkstra(s, n + 1, ds); dijkstra(t, n + 1, dt); compute(s, n, dp1); compute(t, n, dp2); ll Min = 1e18; for(int i = 1; i <= n; i++) { if(ds[t] == ds[i] + dt[i]) { Min = min(Min, dv[i] + min(dp1[i], dp2[i])); } } cout << min(Min, du[v]) << endl; }

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

commuter_pass.cpp: In function 'void dijkstra(int, int, std::vector<long long int>&)':
commuter_pass.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'void compute(int, int, std::vector<long long int>&)':
commuter_pass.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < adj[u].size(); i++) {
                    ^
commuter_pass.cpp: In function 'int main(int, const char**)':
commuter_pass.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m); 
                        ^
commuter_pass.cpp:63:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &s, &t);
                        ^
commuter_pass.cpp:64:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &u, &v);
                        ^
commuter_pass.cpp:67:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &c);
                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...