제출 #364311

#제출 시각아이디문제언어결과실행 시간메모리
364311shafinalamOlympic Bus (JOI20_ho_t4)C++14
11 / 100
35 ms5280 KiB
#include <bits/stdc++.h> using namespace std; const int mxn = 1e5+5; typedef long long ll; #define inf 1e17 typedef pair<ll,ll>pii; ll cost[mxn]; ll dir[mxn]; struct data { int u, v; ll c, d; }; vector<pii>adj[205]; vector<pii>rev[205]; vector<data>edge; ll dis[5][205]; int path[3][205]; int n, m; void dijkstra1(int src, int pos) { vector<int>vis(n+1, 0); dis[pos][src] = 0; priority_queue<pii>pq; pq.push({0LL, src}); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; for(auto it : adj[u]) { ll w = cost[it.second]; int v = it.first; if(dis[pos][u]+w<dis[pos][v]) { dis[pos][v] = dis[pos][u]+w; path[pos][v] = it.second; pq.push({-dis[pos][v], v}); } } } return; } void dijkstra2(int src, int pos) { vector<int>vis(n+1, 0); dis[pos][src] = 0; priority_queue<pii>pq; pq.push({0LL, src}); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; for(auto it : rev[u]) { ll w = cost[it.second]; int v = it.first; if(dis[pos][u]+w<dis[pos][v]) { dis[pos][v] = dis[pos][u]+w; pq.push({-dis[pos][v], v}); } } } return; } ll dijkstra(int src, int idx) { vector<ll>dp(n+5, inf); vector<bool>vis(n+5, 0); dp[src] = 0; priority_queue<pii>pq; pq.push({0, src}); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = 1; for(auto it : adj[u]) { if(idx==it.second) continue; int v = it.first; ll w = cost[it.second]; if(dp[u]+w<dp[v]) { dp[v] = dp[u]+w; pq.push({-dp[v], v}); } } if(u==edge[idx].v) { int x = edge[idx].v; int y = edge[idx].u; ll w = edge[idx].c; if(dp[x]+w<dp[y]) { dp[y] = dp[x]+w; pq.push({-dp[y], y}); } } } if(src==1) return dp[n]; return dp[1]; } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < 5; i++) { for(int r = 0; r <= n; r++) dis[i][r] = inf; } for(int i = 0; i < m; i++) { int u, v; scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]); adj[u].push_back({v, i}); rev[v].push_back({u, i}); edge.push_back({u, v, cost[i], dir[i]}); } dijkstra1(1, 0); dijkstra1(n, 1); dijkstra2(1, 2); dijkstra2(n, 3); ll ans = dis[0][n]+dis[1][1]; for(int i = 0; i < m; i++) { int u = edge[i].u; int v = edge[i].v; ll c = edge[i].c; ll d = edge[i].d; ll res = d; /* if(i==2) { cout << res << '\n'; } */ if(path[0][v]==1) { res+=dijkstra(1, i); } else { res+=min(dis[0][n], dis[0][v]+dis[3][u]+c); } /* if(i==2) { cout << res << '\n'; } */ if(path[1][v]==1) { res+=dijkstra(n, i); } else { res+=min(dis[1][1], dis[1][v]+dis[2][u]+c); } /* if(i==2) { cout << res << '\n'; } */ //cout << res << '\n'; ans = min(ans, res); } if(ans>=inf) { cout << -1 << '\n'; } else { cout << ans << '\n'; } return 0; }

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

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |         scanf("%d%d%lld%lld", &u, &v, &cost[i], &dir[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...