Submission #3282808
Source Code Expand
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
#define ll long long
#define inf 1ll<<60
#define mp make_pair
using namespace std;
priority_queue<pair<ll,int> >Q;
int N,M,S,T;
struct edge{
int to,cost;
int en;
ll expen;
};
vector<int>s[252526],w[252526];
vector<edge>G[25253];
ll dis[25253];
int lim;
bool oh_yeah(){
for(int i=1;i<=N;++i)dis[i]=inf;
Q.push(mp(0,S));
dis[S]=0;
while(Q.size()){
int u=Q.top().second;
Q.pop();
for(auto eg:G[u]){
int v=eg.to;
ll len=dis[u]+eg.cost;
if(len<dis[v]&&len+eg.expen<=lim){
dis[v]=len;
Q.push(mp(-dis[v],v));
}
}
}
if(dis[T]==inf)return 0;
else return 1;
}
int main(){
scanf("%d%d%d%d",&N,&M,&S,&T);
S++,T++;
for(int i=1;i<=M;++i){
int len;
scanf("%d",&len);
int tt;
for(int j=1;j<=len;++j)scanf("%d",&tt),tt++,s[i].push_back(tt);
for(int j=1;j<=len-1;++j)scanf("%d",&tt),w[i].push_back(tt);
ll Cost=0;
for(int j=len-2;j>=0;--j){
G[s[i][j]].push_back((edge){s[i][j+1],w[i][j],s[i][len-1],Cost});
Cost+=w[i][j];
}
Cost=0;
for(int j=0;j<len-1;++j){
G[s[i][j+1]].push_back((edge){s[i][j],w[i][j],s[i][0],Cost});
Cost+=w[i][j];
}
}
for(int i=1;i<=N;++i)dis[i]=inf;
Q.push(mp(0,T));
dis[T]=0;
while(Q.size()){
int u=Q.top().second;
Q.pop();
for(auto eg:G[u]){
int v=eg.to;
ll len=dis[u]+eg.cost;
if(len<dis[v]){
dis[v]=len;
Q.push(mp(-dis[v],v));
}
}
}
for(int u=1;u<=N;++u){
for(auto &eg:G[u]){
eg.expen+=dis[eg.en];
}
}
int l=0,r=999999999;
while(r-l>1){
int mid=l+r>>1;
lim=mid;
if(oh_yeah())r=mid;
else l=mid;
}
cout<<r<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - メンテナンス明け |
User |
chenjingqi |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1799 Byte |
Status |
AC |
Exec Time |
158 ms |
Memory |
17024 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:44:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&N,&M,&S,&T);
^
./Main.cpp:48:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&len);
^
./Main.cpp:50:65: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int j=1;j<=len;++j)scanf("%d",&tt),tt++,s[i].push_back(tt);
^
./Main.cpp:51:62: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int j=1;j<=len-1;++j)scanf("%d",&tt),w[i].push_back(tt);
^
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 |
137 ms |
16896 KB |
large/20_large-01 |
AC |
138 ms |
17024 KB |
large/20_large-02 |
AC |
158 ms |
17024 KB |
large/20_large-03 |
AC |
137 ms |
16896 KB |
large/20_large-04 |
AC |
149 ms |
16896 KB |
large/31_max_large |
AC |
21 ms |
14592 KB |
small/00_sample00 |
AC |
5 ms |
12672 KB |
small/00_sample01 |
AC |
5 ms |
12672 KB |
small/00_sample02 |
AC |
5 ms |
12672 KB |
small/10_small-0000 |
AC |
6 ms |
12672 KB |
small/10_small-0001 |
AC |
6 ms |
12672 KB |
small/10_small-0002 |
AC |
6 ms |
12672 KB |
small/10_small-0003 |
AC |
6 ms |
12672 KB |
small/10_small-0004 |
AC |
6 ms |
12672 KB |
small/10_small-0005 |
AC |
6 ms |
12672 KB |
small/10_small-0006 |
AC |
6 ms |
12672 KB |
small/10_small-0007 |
AC |
6 ms |
12672 KB |
small/10_small-0008 |
AC |
6 ms |
12672 KB |
small/10_small-0009 |
AC |
6 ms |
12672 KB |
small/10_small-0010 |
AC |
6 ms |
12672 KB |
small/10_small-0011 |
AC |
6 ms |
12672 KB |
small/10_small-0012 |
AC |
6 ms |
12672 KB |
small/10_small-0013 |
AC |
5 ms |
12672 KB |
small/10_small-0014 |
AC |
6 ms |
12672 KB |
small/10_small-0015 |
AC |
6 ms |
12672 KB |
small/10_small-0016 |
AC |
6 ms |
12672 KB |
small/10_small-0017 |
AC |
6 ms |
12672 KB |
small/10_small-0018 |
AC |
6 ms |
12672 KB |
small/10_small-0019 |
AC |
6 ms |
12672 KB |
small/30_max_small |
AC |
5 ms |
12672 KB |
small/40_simple_0000 |
AC |
5 ms |
12672 KB |
small/40_simple_0001 |
AC |
5 ms |
12672 KB |
small/40_simple_0002 |
AC |
5 ms |
12672 KB |
small/40_simple_0003 |
AC |
5 ms |
12672 KB |
small/40_simple_0004 |
AC |
5 ms |
12672 KB |
small/40_simple_0005 |
AC |
5 ms |
12672 KB |
small/40_simple_0006 |
AC |
5 ms |
12672 KB |
small/40_simple_0007 |
AC |
5 ms |
12672 KB |
small/40_simple_0008 |
AC |
5 ms |
12672 KB |
small/40_simple_0009 |
AC |
5 ms |
12672 KB |
small/40_simple_0010 |
AC |
5 ms |
12672 KB |
small/40_simple_0011 |
AC |
5 ms |
12672 KB |
small/40_simple_0012 |
AC |
5 ms |
12672 KB |
small/40_simple_0013 |
AC |
5 ms |
12672 KB |
small/40_simple_0014 |
AC |
5 ms |
12672 KB |
small/40_simple_0015 |
AC |
5 ms |
12672 KB |
small/40_simple_0016 |
AC |
5 ms |
12672 KB |
small/40_simple_0017 |
AC |
5 ms |
12672 KB |
small/40_simple_0018 |
AC |
5 ms |
12672 KB |
small/40_simple_0019 |
AC |
5 ms |
12672 KB |
small/90_dijkstra_killer_00 |
AC |
5 ms |
12672 KB |
small/90_dijkstra_killer_01 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_00 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_01 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_02 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_03 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_04 |
AC |
5 ms |
12672 KB |
small/91_tayama_killer_05 |
AC |
5 ms |
12672 KB |