# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
224084 | 2020-04-17T07:40:36 Z | tqbfjotld | Olympic Bus (JOI20_ho_t4) | C++14 | 4 ms | 384 KB |
#include <bits/stdc++.h> using namespace std; #define int long long #define INF 2000000009 int n,m; int dist[205]; vector<pair<int,int> > adjl[205]; vector<pair<int,int> > rev[205]; int c[50005]; int d[50005]; main(){ scanf("%lld%lld",&n,&m); if (m<1000){ for (int x = 0; x<m; x++){ int a,b; scanf("%lld%lld%lld%lld",&a,&b,&c[x],&d[x]); adjl[a].push_back({b,x}); rev[b].push_back({a,x}); } int fans = INF; for (int cov = -1; cov<m; cov++){ priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq; for (int x = 0; x<=n; x++){ dist[x] = INF; } dist[1] = 0; pq.push({0,1}); while (!pq.empty()){ int d = pq.top().first; int node = pq.top().second; pq.pop(); if (d>dist[node]) continue; for (auto x : adjl[node]){ if (x.second==cov) continue; if (dist[node]+c[x.second]<dist[x.first]){ dist[x.first] = dist[node]+c[x.second]; pq.push({dist[x.first],x.first}); } } for (auto x : rev[node]){ if (x.second!=cov) continue; if (dist[node]+c[x.second]<dist[x.first]){ dist[x.first] = dist[node]+c[x.second]; pq.push({dist[x.first],x.first}); } } } int ans = dist[n]; if (ans==INF) continue; for (int x = 0; x<=n; x++){ dist[x] = INF; } dist[n] = 0; pq.push({0,n}); while (!pq.empty()){ int d = pq.top().first; int node = pq.top().second; pq.pop(); if (d>dist[node]) continue; for (auto x : adjl[node]){ if (x.second==cov) continue; if (dist[node]+c[x.second]<dist[x.first]){ dist[x.first] = dist[node]+c[x.second]; pq.push({dist[x.first],x.first}); } } for (auto x : rev[node]){ if (x.second!=cov) continue; if (dist[node]+c[x.second]<dist[x.first]){ dist[x.first] = dist[node]+c[x.second]; pq.push({dist[x.first],x.first}); } } } if (dist[1]==INF) continue; fans = min(fans,ans+dist[1]+d[cov]); } printf("%lld",fans==INF?-1:fans); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |