제출 #1070860

#제출 시각아이디문제언어결과실행 시간메모리
1070860dostsCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
368 ms48772 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e18; const int N = 1e5+50; int n; vector<pii> edges[N]; vi dijkstra(int root) { priority_queue<pii,vector<pii>,greater<pii>> pq; vi dists(n+1,inf); pq.push({0,root}); dists[root] = 0; while (!pq.empty()) { pii f = pq.top(); pq.pop(); if (dists[f.ss] < f.ff) continue; for (auto it : edges[f.ss]) { if (dists[it.ff] > f.ff+it.ss) { dists[it.ff] = f.ff+it.ss; pq.push({f.ff+it.ss,it.ff}); } } } return dists; } void solve() { int m; cin >> n >> m; int a,b,s,t; cin >> a >> b >> s >> t; for (int i=1;i<=m;i++) { int a,b,c; cin >> a >> b >> c; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } vi da = dijkstra(a); vi db = dijkstra(b); using state = pair<int,pair<int,pair<pii,int>>>; int dp[n+1][2][2][2]; for (int i=0;i<=n;i++) { for (int j=0;j<2;j++) { for (int jj=0;jj<2;jj++) { for (int jjj=0;jjj<2;jjj++) { dp[i][j][jj][jjj] = inf; } } } } dp[s][0][0][0] = 0; priority_queue<state,vector<state>,greater<state>> pq; pq.push({0,{s,{{0,0},0}}}); while (!pq.empty()) { state f = pq.top(); int city = f.ss.ff; int cost = f.ff; int ever = f.ss.ss.ff.ff; int cur = f.ss.ss.ff.ss; int dir = f.ss.ss.ss; pq.pop(); if (dp[city][ever][cur][dir] < cost) continue; if (!(ever && !cur)) { for (auto& [go,w] : edges[city]) { if ((da[city]+w+db[go]!=da[b] && db[city]+w+da[go] != da[b])) continue; if (ever && (dir != db[go]>db[city])) continue; if (dp[go][1][cur|1][db[go]>db[city]] > cost){ dp[go][1][cur|1][db[go]>db[city]] = cost; pq.push({cost,{go,{{1,cur|1},db[go]>db[city]}}}); } } } for (auto& [go,w] : edges[city]) { if (dp[go][ever][0][dir] > cost+w){ dp[go][ever][0][dir] = cost+w; pq.push({cost+w,{go,{{ever,0},dir}}}); } } } int ans = inf; for (int i=0;i<2;i++) for (int j=0;j<2;j++) for (int jj=0;jj<2;jj++) ans = min(ans,dp[t][i][j][jj]); cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }

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

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:75:43: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   75 |                 if (ever && (dir != db[go]>db[city])) continue;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...