제출 #1044242

#제출 시각아이디문제언어결과실행 시간메모리
1044242OtalpRobot (JOI21_ho_t4)C++14
0 / 100
1483 ms145880 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pb push_back #define ff first #define ss second vector<pii> q[200100]; pii d[200100]; map<int, int> dd[200100]; map<int, vector<pii>> dq[200100]; map<int, ll> dp[200100]; map<int, int> us[200100]; void solve(){ int n, m; cin>>n>>m; for(int i=1; i<=m; i++){ int l, r, x, c; cin>>l>>r>>x>>c; q[l].pb({r, i}); q[r].pb({l, i}); d[i] = {x, c}; } for(int i=1; i<=n; i++){ for(pii h: q[i]){ int to = h.ff; int e = h.ss; dd[i][d[e].ff] += d[e].ss; dq[i][d[e].ff].pb(h); } } set<pair<ll, pii>> s; s.insert({0, {1, 0}}); while(s.size()){ auto it = s.begin(); int v = it -> ss.ff, k = it -> ss.ss; if(us[v][k]){ s.erase(s.begin()); continue; } us[v][k] = 1; dp[v][k] = it -> ff; //cout<<v<<' '<<k<<' '<<dp[v][k]<<'\n'; s.erase(it); if(k == 0){ for(pii h: q[v]){ int to = h.ff; int c = d[h.ss].ff; int g = d[h.ss].ss; s.insert({dp[v][k] + dd[v][c] - g, {to, 0}}); s.insert({dp[v][k] + dd[to][c], {to, c}}); s.insert({dp[v][k] + g, {to, 0}}); } } else{ for(pii h: dq[v][k]){ int to = h.ff; int c = d[h.ss].ff; int g = d[h.ss].ss; s.insert({dp[v][k] - g, {to, 0}}); s.insert({dp[v][k] - g + dd[to][c], {to, c}}); s.insert({dp[v][k] + g, {to, 0}}); } } } ll ans = 1e18; for(int i=0; i<=m; i++){ if(us[n][i]) ans = min(ans, dp[n][i]); } if(ans == 1e18) cout<<-1; else cout<<ans; } signed main(){ solve(); }

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

Main.cpp: In function 'void solve()':
Main.cpp:30:17: warning: unused variable 'to' [-Wunused-variable]
   30 |             int to = h.ff;
      |                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...