# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
226469 |
2020-04-23T22:36:05 Z |
thebes |
Olympic Bus (JOI20_ho_t4) |
C++14 |
|
1000 ms |
161656 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
#define pb push_back
const int MN = 202, MM = 5e4+5;
int N, M, i, j, x, y, w[MM], c[MM], u[MM], vs[MN], ban[MM]; ll ans, dis[MN], a[MM][MN], b[MM][MN], cost[MM];
vector<pii> adj[MN], rev[MN];
vi tree; pii ed[MM];
struct idk{ll x, t, p;};
struct pq{bool operator()(const idk&i,const idk&j){return i.t>j.t;}};
priority_queue<idk,vector<idk>,pq> q;
void dij(int src,bool dir){
q.push({src,0,-1});
memset(vs,0,sizeof(vs));
for(i=1;i<=N;i++)
dis[i]=1LL<<55;
while(q.size()){
idk cur=q.top(); q.pop();
if(vs[cur.x]) continue;
vs[cur.x]=1;
dis[cur.x]=cur.t;
if(cur.p!=-1) u[cur.p]=1;
if(dir==1){
for(auto v : adj[cur.x]){
if(ban[v.second]||vs[v.first]) continue;
q.push({v.first,cur.t+w[v.second],v.second});
}
}
else{
for(auto v : rev[cur.x]){
if(ban[v.second]||vs[v.first]) continue;
q.push({v.first,cur.t+w[v.second],v.second});
}
}
}
}
int main(){
for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
scanf("%d%d%d%d",&x,&y,&w[i],&c[i]);
ed[i]={x,y};
adj[x].pb({y,i});
rev[y].pb({x,i});
}
for(int k=0;k<2;k++){
memset(u,0,sizeof(u));
dij(1,1^k);
tree.clear();
for(i=1;i<=M;i++){
if(u[i]) tree.pb(i);
else{
for(j=1;j<=N;j++)
a[i][j]=dis[j];
}
}
assert(tree.size()<=N);
for(auto v : tree){
ban[v]=1;
dij(1,1^k);
for(j=1;j<=N;j++)
a[v][j]=dis[j];
ban[v]=0;
}
memset(u,0,sizeof(u));
dij(N,k);
tree.clear();
for(i=1;i<=M;i++){
if(u[i]) tree.pb(i);
else{
for(j=1;j<=N;j++)
b[i][j]=dis[j];
}
}
assert(tree.size()<=N);
for(auto v : tree){
ban[v]=1;
dij(N,k);
for(j=1;j<=N;j++)
b[v][j]=dis[j];
ban[v]=0;
}
for(j=1;j<=M;j++){
if(!k) cost[j]+=min(a[j][N],a[j][ed[j].second]+w[j]+b[j][ed[j].first]);
else cost[j]+=min(a[j][N],a[j][ed[j].first]+w[j]+b[j][ed[j].second]);
}
}
dij(1,1);
ans+=dis[N];
dij(N,0);
ans+=dis[1];
for(j=1;j<=M;j++)
ans=min(ans,cost[j]+c[j]);
if(ans>(1LL<<55)) printf("-1\n");
else printf("%lld\n",ans);
return 0;
}
Compilation message
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from ho_t4.cpp:1:
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:63:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(tree.size()<=N);
~~~~~~~~~~~^~~
ho_t4.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(tree.size()<=N);
~~~~~~~~~~~^~~
ho_t4.cpp:46:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
~~~~~~~~~~~~~~~~~~~^~~~
ho_t4.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&x,&y,&w[i],&c[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
3840 KB |
Output is correct |
2 |
Correct |
6 ms |
1408 KB |
Output is correct |
3 |
Incorrect |
48 ms |
3840 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1107 ms |
161656 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
3840 KB |
Output is correct |
2 |
Correct |
7 ms |
1408 KB |
Output is correct |
3 |
Execution timed out |
1055 ms |
126492 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
3840 KB |
Output is correct |
2 |
Correct |
6 ms |
1408 KB |
Output is correct |
3 |
Incorrect |
48 ms |
3840 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |