# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
224093 | 2020-04-17T07:53:38 Z | tqbfjotld | Olympic Bus (JOI20_ho_t4) | C++14 | 96 ms | 2552 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]; int adjm[405][405]; main(){ scanf("%lld%lld",&n,&m); for (int x = 0; x<=2*n; x++){ for (int y = 0; y<=2*n; y++){ adjm[x][y] = INF; if (x==y) adjm[x][y] = 0; } } for (int x = 0; x<m; x++){ int a,b,c,d; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); adjm[a][b] = min(adjm[a][b],c); adjm[a+n][b+n] = min(adjm[a+n][b+n],c); adjm[b][a+n] = min(adjm[b][a+n],c+d); } for (int k = 1; k<=2*n; k++){ for (int i = 1; i<=2*n; i++){ for (int j = 1; j<=2*n; j++){ adjm[i][j] = min(adjm[i][j],adjm[i][k]+adjm[k][j]); } } } int ans1 = min(adjm[1][n]+adjm[n][1],adjm[1][2*n]+adjm[2*n][n+1]); ans1 = min(ans1,adjm[1][n]+adjm[n][n+1]); printf("%lld",ans1>=INF?-1:ans1); return 0; 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 1536 KB | Output is correct |
2 | Correct | 73 ms | 1664 KB | Output is correct |
3 | Correct | 76 ms | 1536 KB | Output is correct |
4 | Correct | 73 ms | 1656 KB | Output is correct |
5 | Correct | 5 ms | 512 KB | Output is correct |
6 | Correct | 74 ms | 1656 KB | Output is correct |
7 | Incorrect | 4 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 94 ms | 1536 KB | Output is correct |
2 | Correct | 93 ms | 2432 KB | Output is correct |
3 | Correct | 94 ms | 2432 KB | Output is correct |
4 | Correct | 73 ms | 1664 KB | Output is correct |
5 | Correct | 73 ms | 1664 KB | Output is correct |
6 | Correct | 73 ms | 1664 KB | Output is correct |
7 | Correct | 74 ms | 1656 KB | Output is correct |
8 | Correct | 4 ms | 384 KB | Output is correct |
9 | Incorrect | 96 ms | 2432 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 78 ms | 1536 KB | Output is correct |
2 | Correct | 72 ms | 1656 KB | Output is correct |
3 | Correct | 89 ms | 1536 KB | Output is correct |
4 | Correct | 81 ms | 1792 KB | Output is correct |
5 | Correct | 92 ms | 2552 KB | Output is correct |
6 | Incorrect | 5 ms | 384 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 1536 KB | Output is correct |
2 | Correct | 73 ms | 1664 KB | Output is correct |
3 | Correct | 76 ms | 1536 KB | Output is correct |
4 | Correct | 73 ms | 1656 KB | Output is correct |
5 | Correct | 5 ms | 512 KB | Output is correct |
6 | Correct | 74 ms | 1656 KB | Output is correct |
7 | Incorrect | 4 ms | 384 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |