Submission #1334268
Source Code Expand
#include<bits/stdc++.h> using namespace std; struct edge{int to,cost,num,pre,dir;}; int n,m,s,t,dist[30000],dp[30000];vector<edge>x[30000];vector<int>F[30000],G[30000],H[30000]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Q; bool solve(int p){ if(p<0)return false; for(int i=0;i<n;i++)dp[i]=1e9; dp[s]=0;Q.push(make_pair(0,s)); while(!Q.empty()){ int a1=Q.top().first,a2=Q.top().second;Q.pop(); for(int i=0;i<x[a2].size();i++){ int to1=x[a2][i].to,cost1=x[a2][i].cost; int D=0; if(x[a2][i].dir==1){ D=dist[F[x[a2][i].num][0]]; D+=H[x[a2][i].num][x[a2][i].pre]; } if(x[a2][i].dir==0){ D=dist[F[x[a2][i].num][F[x[a2][i].num].size()-1]]; D+=H[x[a2][i].num][H[x[a2][i].num].size()-1]-H[x[a2][i].num][x[a2][i].pre]; } if(D+a1>p)continue; if(dp[to1]>a1+cost1){ dp[to1]=a1+cost1;Q.push(make_pair(dp[to1],to1)); } } } if(dp[t]<5e8)return true; return false; } int main(){ cin>>n>>m>>s>>t; for(int i=0;i<m;i++){ int a;cin>>a; for(int j=0;j<a;j++){int b;cin>>b;F[i].push_back(b);} for(int j=0;j<a-1;j++){int b;cin>>b;G[i].push_back(b);} H[i].push_back(0);for(int j=0;j<G[i].size();j++)H[i].push_back(H[i][j]+G[i][j]); for(int j=0;j<a-1;j++){ x[F[i][j]].push_back(edge{F[i][j+1],G[i][j],i,j,0}); x[F[i][j+1]].push_back(edge{F[i][j],G[i][j],i,j+1,1}); } } for(int i=0;i<n;i++)dist[i]=1e9; dist[t]=0;Q.push(make_pair(0,t)); while(!Q.empty()){ int a1=Q.top().first,a2=Q.top().second;Q.pop(); for(int i=0;i<x[a2].size();i++){ if(dist[x[a2][i].to]>dist[a2]+x[a2][i].cost){ dist[x[a2][i].to]=dist[a2]+x[a2][i].cost; Q.push(make_pair(dist[x[a2][i].to],x[a2][i].to)); } } } int L=0,R=500000000,M; while(true){ M=(L+R)/2; bool p1=solve(M-1),p2=solve(M); if(p1==false && p2==true){cout<<M<<endl;return 0;} if(p1==true)R=M;else L=M; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | E869120 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1935 Byte |
Status | AC |
Exec Time | 363 ms |
Memory | 7040 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 | 298 ms | 6912 KB |
large/20_large-01 | AC | 309 ms | 7040 KB |
large/20_large-02 | AC | 363 ms | 7040 KB |
large/20_large-03 | AC | 288 ms | 6912 KB |
large/20_large-04 | AC | 318 ms | 6912 KB |
large/31_max_large | AC | 45 ms | 4736 KB |
small/00_sample00 | AC | 3 ms | 3072 KB |
small/00_sample01 | AC | 3 ms | 3072 KB |
small/00_sample02 | AC | 3 ms | 3072 KB |
small/10_small-0000 | AC | 5 ms | 3072 KB |
small/10_small-0001 | AC | 4 ms | 3072 KB |
small/10_small-0002 | AC | 4 ms | 3072 KB |
small/10_small-0003 | AC | 4 ms | 3072 KB |
small/10_small-0004 | AC | 4 ms | 3072 KB |
small/10_small-0005 | AC | 4 ms | 3072 KB |
small/10_small-0006 | AC | 4 ms | 3072 KB |
small/10_small-0007 | AC | 4 ms | 3072 KB |
small/10_small-0008 | AC | 4 ms | 3072 KB |
small/10_small-0009 | AC | 4 ms | 3072 KB |
small/10_small-0010 | AC | 4 ms | 3072 KB |
small/10_small-0011 | AC | 4 ms | 3072 KB |
small/10_small-0012 | AC | 4 ms | 3072 KB |
small/10_small-0013 | AC | 4 ms | 3072 KB |
small/10_small-0014 | AC | 4 ms | 3072 KB |
small/10_small-0015 | AC | 4 ms | 3072 KB |
small/10_small-0016 | AC | 4 ms | 3072 KB |
small/10_small-0017 | AC | 4 ms | 3072 KB |
small/10_small-0018 | AC | 4 ms | 3072 KB |
small/10_small-0019 | AC | 4 ms | 3072 KB |
small/30_max_small | AC | 3 ms | 3072 KB |
small/40_simple_0000 | AC | 2 ms | 3072 KB |
small/40_simple_0001 | AC | 3 ms | 3072 KB |
small/40_simple_0002 | AC | 2 ms | 3072 KB |
small/40_simple_0003 | AC | 3 ms | 3072 KB |
small/40_simple_0004 | AC | 3 ms | 3072 KB |
small/40_simple_0005 | AC | 3 ms | 3072 KB |
small/40_simple_0006 | AC | 3 ms | 3072 KB |
small/40_simple_0007 | AC | 3 ms | 3072 KB |
small/40_simple_0008 | AC | 3 ms | 3072 KB |
small/40_simple_0009 | AC | 3 ms | 3072 KB |
small/40_simple_0010 | AC | 3 ms | 3072 KB |
small/40_simple_0011 | AC | 3 ms | 3072 KB |
small/40_simple_0012 | AC | 3 ms | 3072 KB |
small/40_simple_0013 | AC | 3 ms | 3072 KB |
small/40_simple_0014 | AC | 3 ms | 3072 KB |
small/40_simple_0015 | AC | 3 ms | 3072 KB |
small/40_simple_0016 | AC | 3 ms | 3072 KB |
small/40_simple_0017 | AC | 3 ms | 3072 KB |
small/40_simple_0018 | AC | 3 ms | 3072 KB |
small/40_simple_0019 | AC | 3 ms | 3072 KB |
small/90_dijkstra_killer_00 | AC | 3 ms | 3072 KB |
small/90_dijkstra_killer_01 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_00 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_01 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_02 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_03 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_04 | AC | 3 ms | 3072 KB |
small/91_tayama_killer_05 | AC | 3 ms | 3072 KB |