제출 #1062006

#제출 시각아이디문제언어결과실행 시간메모리
1062006_rain_Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
442 ms31104 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; #define debug false void SETIO(string name) { if (name=="") return; freopen((name + ".inp").c_str(),"r",stdin); freopen((name + ".out").c_str(),"w",stdout); return; } const int maxn = 2e5; const i64 INF = 1e18; vector<pair<int,int>> g[maxn+2]; int u[maxn+2],v[maxn+2],c[maxn+2]; #define fi first #define se second int n , m , source , sink , nsource , nsink; struct _D { i64 val; i64 rem; int u; int t; bool operator <(const _D & other) const { if (other.val != val) return other.val < val; if (other.rem != rem) return other.rem < rem; } } ; bool vis[maxn+2][2]; vector<i64> dist[2]; i64 dp[maxn+2][2]; i64 mn ; vector<i64> djisktra(int source) { vector<i64> d; d.assign(n+2,INF); d[source] = 0; priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> q; q.push({d[source] , source}); while (q.size()) { int u = q.top().se; i64 val = q.top().fi; q.pop(); if (d[u] != val) continue; for (auto& v : g[u]) { if (d[v.first] > d[u] + v.second) { d[v.first] = d[u] + v.second; q.push({d[v.first] , v.first}); } } } return d; } int trans(int v , int t , int t1 , int t2){ if (t==1) return t; if (t==0){ if (dist[t1][v] + dist[t2][v] == mn) return 1; } return 0; } i64 cost(int v , int w , i64 rem , int t , int t1 , int t2){ if (t==0){ if (dist[t1][v] + dist[t2][v] == mn) return 0; return w; } if (t==1){ if (rem==INF) return w; if (dist[t1][v] + dist[t2][v] == mn && rem + w == dist[t1][v]) return 0; return w; } return INF; } i64 calc(int s , int snk , int t1 , int t2) { memset(vis,0,sizeof vis); memset(dp,0x3f,sizeof dp); priority_queue<_D> q; int zz = trans(s,0,t1,t2); dp[s][zz] = 0; if (zz==1) q.push({dp[s][zz] , dist[t1][s] , s , 1}); else q.push({dp[s][zz] , INF , s , 0}); if (debug){ cout << "START THE SEASON\n"; cout << t1 << ' ' << t2 << '\n'; } while (q.size()){ int u = q.top().u , t = q.top().t; i64 val = q.top().val , rem = q.top().rem; q.pop(); if (vis[u][t]) continue; vis[u][t]=true; dp[u][t]=val; if (debug){ cout << "DEBUG\n"; cout << dp[u][t] << ' ' << u << ' ' << t << '\n'; } for (auto& v : g[u]){ int to = v.first , w = v.second; int nxt = trans(to , t , t1 , t2); if (vis[to][nxt]) continue; i64 c = cost(to , w , rem , t , t1 , t2); if (debug){ cout << "( SHOW OUT FOR THE CASE : " << u << ')' << '\n'; cout << u << " -> " << to << ' ' << w << ' ' << nxt << ' ' << c << '\n'; cout << dist[t1][to] << ' ' << dist[t2][to] << ' ' << mn << '\n'; cout << '\n'; } if (t == 0){ if (nxt==0) q.push({val + w , INF , to , 0}); else q.push({val + w , dist[t1][to] , to , 1}); } if (t == 1){ if (c > 0) q.push({val + w , INF , to , 1}); else q.push({val , dist[t1][to] , to , 1}); } } } return min(dp[snk][0],dp[snk][1]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); SETIO(""); cin >> n >> m; cin >> source >> sink; cin >> nsource >> nsink; for (int i = 1; i <= m; ++i){ cin >> u[i] >> v[i] >> c[i]; g[u[i]].push_back({v[i],c[i]}); g[v[i]].push_back({u[i],c[i]}); } dist[0] = djisktra(source); dist[1] = djisktra(sink); mn = dist[0][sink]; if (debug){ cout << "MINIMUM DIST : " << mn << '\n'; } cout << min({calc(nsource,nsink,0,1),calc(nsource , nsink,1,0),calc(nsink,nsource,0,1),calc(nsink,nsource,1,0)}); }

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

commuter_pass.cpp: In function 'void SETIO(std::string)':
commuter_pass.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen((name + ".inp").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((name + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In member function 'bool _D::operator<(const _D&) const':
commuter_pass.cpp:31:2: warning: control reaches end of non-void function [-Wreturn-type]
   31 |  }
      |  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...