제출 #516393

#제출 시각아이디문제언어결과실행 시간메모리
516393XIIRobot (JOI21_ho_t4)C++17
0 / 100
992 ms77112 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second #define mp make_pair #define eb emplace_back #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORU(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define IOS cin.tie(0)->sync_with_stdio(false); #define PROB "JOI21_ho_t4" void Fi(){ if(fopen(PROB".inp", "r")){ freopen(PROB".inp", "r", stdin); freopen(PROB".out", "w", stdout); } } const int N = 1e5 + 1; const ll INF = 1e18; int n, m; using pi = pair<int, int>; map<int, vector<pi>> adj[N]; map<int, ll> tot[N], dp2[N]; ll dp[N][2]; using T = pair<ll, pair<int, int>>; priority_queue<T, vector<T>, greater<T>> pq; ll dijkstra(const int &s, const int &e){ fill(dp[0] + 1, dp[0] + n + 1, INF); pq.emplace(0, mp(s, 0)); dp[s][0] = 0; dp[e][0] = INF; while(!pq.empty()){ ll wu = pq.top().fi; auto [u, cu] = pq.top().se; pq.pop(); if(cu){ if(dp2[u][cu] != wu) continue; for(auto [v, wv]: adj[u][cu]){ ll w = wu + (tot[u][cu] - wv); if(dp[v][0] > w){ dp[v][0] = w; pq.emplace(dp[v][0], mp(v, 0)); } } } else{ if(dp[u][0] != wu) continue; for(auto [cv, ed]: adj[u]){ for(auto [v, wv]: ed){ ll case1 = wu + wv; if((v != s && !dp[v][0]) || dp[v][0] > case1){ dp[v][0] = case1; pq.emplace(dp[v][0], mp(v, 0)); } ll case2 = wu + (tot[u][cv] - wv); if((v != s && !dp[v][0]) || dp[v][0] > case2){ dp[v][0] = case2; pq.emplace(dp[v][0], mp(v, 0)); } ll case3 = wu; if(!dp2[v].count(cv) || dp2[v][cv] > case3){ dp2[v][cv] = case3; pq.emplace(dp2[v][cv], mp(v, cv)); } } } } } return (dp[e][0] == INF ? -1 : dp[e][0]); } int main(){ IOS; Fi(); cin >> n >> m; FORU(i, 1, m){ int u, v, c, p; cin >> u >> v >> c >> p; adj[u][c].eb(v, p); adj[v][c].eb(u, p); tot[u][c] += p; tot[v][c] += p; } cout << dijkstra(1, n); return 0; }

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

Main.cpp: In function 'void Fi()':
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...