제출 #887989

#제출 시각아이디문제언어결과실행 시간메모리
887989hariaakas646Olympic Bus (JOI20_ho_t4)C++17
5 / 100
1069 ms4944 KiB
#include <bits/stdc++.h> using namespace std; #define scd(x) scanf("%d", &x) #define sclld(x) scanf("%lld", &x) #define frange(i, n) for(int i=0; i<n; i++) #define forr(i, l, r) for(int i=l; i<r; i++) #define all(vec) vec.begin(), vec.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long lli; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pii> vii; typedef vector<lli> vll; typedef vector<vi> vvi; typedef vector<bool> vb; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); } int main() { // usaco(); int n, m; scd(n); scd(m); vector<pair<pii, pair<lli, lli>>> vec(m); vector<set<int>> graph(n+1); frange(i, m) { int u, v; scd(u); scd(v); lli c, d; sclld(c); sclld(d); graph[u].insert(i); vec[i] = mp(mp(u, v), mp(c, d)); } vll dist(n+1, 1e18); priority_queue<pair<lli, int>> pq; vb vis(n+1); pq.push(mp(0, 1)); dist[1] = 0; while(pq.size()) { auto p = pq.top(); pq.pop(); if(vis[p.s]) continue; vis[p.s] = true; for(auto i : graph[p.s]) { auto e = vec[i]; if(dist[p.s] + e.s.f < dist[e.f.s]) { dist[e.f.s] = dist[p.s] + e.s.f; pq.push(mp(-dist[e.f.s], e.f.s)); } } } lli v = dist[n]; dist = vll(n+1, 1e18); vis = vb(n+1); pq.push(mp(0, n)); dist[n] = 0; while(pq.size()) { auto p = pq.top(); pq.pop(); if(vis[p.s]) continue; vis[p.s] = true; for(auto i : graph[p.s]) { auto e = vec[i]; if(dist[p.s] + e.s.f < dist[e.f.s]) { dist[e.f.s] = dist[p.s] + e.s.f; pq.push(mp(-dist[e.f.s], e.f.s)); } } } v += dist[1]; lli mi = v; frange(i, m) { auto p = vec[i]; graph[p.f.f].erase(i); graph[p.f.s].insert(i); swap(vec[i].f.f, vec[i].f.s); vll dist(n+1, 1e18); priority_queue<pair<lli, int>> pq; vb vis(n+1); pq.push(mp(0, 1)); dist[1] = 0; while(pq.size()) { auto p = pq.top(); pq.pop(); if(vis[p.s]) continue; vis[p.s] = true; for(auto i : graph[p.s]) { auto e = vec[i]; if(dist[p.s] + e.s.f < dist[e.f.s]) { dist[e.f.s] = dist[p.s] + e.s.f; pq.push(mp(-dist[e.f.s], e.f.s)); } } } lli v = dist[n]; dist = vll(n+1, 1e18); vis = vb(n+1); pq.push(mp(0, n)); dist[n] = 0; while(pq.size()) { auto p = pq.top(); pq.pop(); if(vis[p.s]) continue; vis[p.s] = true; for(auto i : graph[p.s]) { auto e = vec[i]; if(dist[p.s] + e.s.f < dist[e.f.s]) { dist[e.f.s] = dist[p.s] + e.s.f; pq.push(mp(-dist[e.f.s], e.f.s)); } } } v += dist[1]; mi = min(mi, v+vec[i].s.s); p = vec[i]; graph[p.f.f].erase(i); graph[p.f.s].insert(i); swap(vec[i].f.f, vec[i].f.s); } if(mi < 1e17) printf("%lld", mi); else printf("-1"); }

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

ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:30:2: note: in expansion of macro 'scd'
   30 |  scd(n);
      |  ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:31:2: note: in expansion of macro 'scd'
   31 |  scd(m);
      |  ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:38:3: note: in expansion of macro 'scd'
   38 |   scd(u);
      |   ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(x) scanf("%d", &x)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:39:3: note: in expansion of macro 'scd'
   39 |   scd(v);
      |   ^~~
ho_t4.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(x) scanf("%lld", &x)
      |                  ~~~~~^~~~~~~~~~~~
ho_t4.cpp:41:3: note: in expansion of macro 'sclld'
   41 |   sclld(c);
      |   ^~~~~
ho_t4.cpp:6:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | #define sclld(x) scanf("%lld", &x)
      |                  ~~~~~^~~~~~~~~~~~
ho_t4.cpp:42:3: note: in expansion of macro 'sclld'
   42 |   sclld(d);
      |   ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...