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
AC × 52
AC × 6
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