Submission #616861
Source Code Expand
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef long long ll; ll inf=1e11; typedef pair<int,ll> P; struct edge{ int to,mis; ll c,mc; edge(int a,int b,ll c,ll d) :to(a),mis(b),c(c),mc(d){} }; vector<edge> G[25252]; int N,M,s,t; int tmp[25252],tc[25252]; ll d0[25252],d[25252]; void dijkstra(ll T){ rep(i,N) d[i]=inf; d[s]=0; priority_queue<P,vector<P>,greater<P> > que; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.sc; if(d[v]<p.fs) continue; for(edge e:G[v]) if(d[v]+e.mc+d0[e.mis]<=T){ if(d[e.to]>d[v]+e.c){ d[e.to]=d[v]+e.c; que.push(P(d[e.to],e.to)); } } } } int main(){ cin>>N>>M>>s>>t; rep(i,M){ int L; cin>>L; rep(i,L) cin>>tmp[i]; rep(i,L-1) cin>>tc[i]; ll sum=0; for(int i=L-2;i>=0;i--){ sum+=tc[i]; G[tmp[i]].pb(edge(tmp[i+1],tmp[L-1],tc[i],sum)); } sum=0; for(int i=1;i<=L-1;i++){ sum+=tc[i-1]; G[tmp[i]].pb(edge(tmp[i-1],tmp[0],tc[i-1],sum)); } } rep(i,N) d0[i]=inf; d0[t]=0; priority_queue<P,vector<P>,greater<P> > que; que.push(P(0,t)); while(!que.empty()){ P p=que.top(); que.pop(); int v=p.sc; if(d0[v]<p.fs) continue; for(edge e:G[v]){ if(d0[e.to]>d0[v]+e.c){ d0[e.to]=d0[v]+e.c; que.push(P(d0[e.to],e.to)); } } } ll ub=1e10,lb=0; while(ub-lb>1){ ll T=(ub+lb)/2; dijkstra(T); if(d[t]<=T) ub=T; else lb=T; } cout<<ub<<endl; }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | sigma425 |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1759 Byte |
Status | AC |
Exec Time | 401 ms |
Memory | 5572 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 | large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/20_large-00 | AC | 340 ms | 5572 KB |
large/20_large-01 | AC | 329 ms | 5552 KB |
large/20_large-02 | AC | 401 ms | 5552 KB |
large/20_large-03 | AC | 352 ms | 5492 KB |
large/20_large-04 | AC | 349 ms | 5512 KB |
large/31_max_large | AC | 69 ms | 3492 KB |
small/00_sample00 | AC | 26 ms | 1428 KB |
small/00_sample01 | AC | 24 ms | 1440 KB |
small/00_sample02 | AC | 26 ms | 1316 KB |
small/10_small-0000 | AC | 29 ms | 1440 KB |
small/10_small-0001 | AC | 25 ms | 1564 KB |
small/10_small-0002 | AC | 26 ms | 1568 KB |
small/10_small-0003 | AC | 25 ms | 1560 KB |
small/10_small-0004 | AC | 26 ms | 1444 KB |
small/10_small-0005 | AC | 30 ms | 1448 KB |
small/10_small-0006 | AC | 27 ms | 1484 KB |
small/10_small-0007 | AC | 40 ms | 1400 KB |
small/10_small-0008 | AC | 28 ms | 1444 KB |
small/10_small-0009 | AC | 27 ms | 1432 KB |
small/10_small-0010 | AC | 28 ms | 1444 KB |
small/10_small-0011 | AC | 29 ms | 1448 KB |
small/10_small-0012 | AC | 28 ms | 1440 KB |
small/10_small-0013 | AC | 31 ms | 1440 KB |
small/10_small-0014 | AC | 27 ms | 1444 KB |
small/10_small-0015 | AC | 28 ms | 1452 KB |
small/10_small-0016 | AC | 28 ms | 1436 KB |
small/10_small-0017 | AC | 28 ms | 1444 KB |
small/10_small-0018 | AC | 26 ms | 1560 KB |
small/10_small-0019 | AC | 27 ms | 1320 KB |
small/30_max_small | AC | 27 ms | 1312 KB |
small/40_simple_0000 | AC | 27 ms | 1320 KB |
small/40_simple_0001 | AC | 26 ms | 1440 KB |
small/40_simple_0002 | AC | 26 ms | 1312 KB |
small/40_simple_0003 | AC | 27 ms | 1312 KB |
small/40_simple_0004 | AC | 25 ms | 1440 KB |
small/40_simple_0005 | AC | 26 ms | 1316 KB |
small/40_simple_0006 | AC | 27 ms | 1320 KB |
small/40_simple_0007 | AC | 30 ms | 1316 KB |
small/40_simple_0008 | AC | 27 ms | 1316 KB |
small/40_simple_0009 | AC | 26 ms | 1316 KB |
small/40_simple_0010 | AC | 26 ms | 1316 KB |
small/40_simple_0011 | AC | 26 ms | 1316 KB |
small/40_simple_0012 | AC | 26 ms | 1316 KB |
small/40_simple_0013 | AC | 28 ms | 1444 KB |
small/40_simple_0014 | AC | 27 ms | 1316 KB |
small/40_simple_0015 | AC | 25 ms | 1444 KB |
small/40_simple_0016 | AC | 24 ms | 1436 KB |
small/40_simple_0017 | AC | 24 ms | 1308 KB |
small/40_simple_0018 | AC | 27 ms | 1308 KB |
small/40_simple_0019 | AC | 32 ms | 1408 KB |
small/90_dijkstra_killer_00 | AC | 27 ms | 1368 KB |
small/90_dijkstra_killer_01 | AC | 27 ms | 1312 KB |
small/91_tayama_killer_00 | AC | 28 ms | 1376 KB |
small/91_tayama_killer_01 | AC | 28 ms | 1300 KB |
small/91_tayama_killer_02 | AC | 28 ms | 1432 KB |
small/91_tayama_killer_03 | AC | 28 ms | 1432 KB |
small/91_tayama_killer_04 | AC | 28 ms | 1432 KB |
small/91_tayama_killer_05 | AC | 28 ms | 1300 KB |