Submission #3053642


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 0x3f3f3f3f3f3f
#define mp make_pair
using namespace std;
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 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;
	priority_queue<pair<ll,int> >Q;
	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;
		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<=mid){
					dis[v]=len;
					Q.push(mp(-dis[v],v));
				}	
			}
		}
		if(dis[T]==inf)l=mid;
		else r=mid;
	}
	printf("%d",r);
	return 0;
}

Submission Info

Submission Time
Task C - メンテナンス明け
User chenjingqi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1736 Byte
Status WA
Exec Time 162 ms
Memory 17024 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:23: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:27:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&len);
                   ^
./Main.cpp:29: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:30: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 0 / 50 0 / 50
Status
WA × 52
WA × 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 WA 141 ms 16896 KB
large/20_large-01 WA 141 ms 17024 KB
large/20_large-02 WA 162 ms 17024 KB
large/20_large-03 WA 140 ms 16896 KB
large/20_large-04 WA 153 ms 16896 KB
large/31_max_large WA 21 ms 14592 KB
small/00_sample00 WA 5 ms 12672 KB
small/00_sample01 WA 5 ms 12672 KB
small/00_sample02 WA 5 ms 12672 KB
small/10_small-0000 WA 6 ms 12672 KB
small/10_small-0001 WA 6 ms 12672 KB
small/10_small-0002 WA 6 ms 12672 KB
small/10_small-0003 WA 6 ms 12672 KB
small/10_small-0004 WA 6 ms 12672 KB
small/10_small-0005 WA 6 ms 12672 KB
small/10_small-0006 WA 6 ms 12672 KB
small/10_small-0007 WA 6 ms 12672 KB
small/10_small-0008 WA 6 ms 12672 KB
small/10_small-0009 WA 6 ms 12672 KB
small/10_small-0010 WA 5 ms 12672 KB
small/10_small-0011 WA 6 ms 12672 KB
small/10_small-0012 WA 6 ms 12672 KB
small/10_small-0013 WA 6 ms 12672 KB
small/10_small-0014 WA 6 ms 12672 KB
small/10_small-0015 WA 6 ms 12672 KB
small/10_small-0016 WA 6 ms 12672 KB
small/10_small-0017 WA 6 ms 12672 KB
small/10_small-0018 WA 6 ms 12672 KB
small/10_small-0019 WA 6 ms 12672 KB
small/30_max_small WA 5 ms 12672 KB
small/40_simple_0000 WA 5 ms 12672 KB
small/40_simple_0001 WA 5 ms 12672 KB
small/40_simple_0002 WA 5 ms 12672 KB
small/40_simple_0003 WA 5 ms 12672 KB
small/40_simple_0004 WA 5 ms 12672 KB
small/40_simple_0005 WA 5 ms 12672 KB
small/40_simple_0006 WA 5 ms 12672 KB
small/40_simple_0007 WA 5 ms 12672 KB
small/40_simple_0008 WA 5 ms 12672 KB
small/40_simple_0009 WA 5 ms 12672 KB
small/40_simple_0010 WA 5 ms 12672 KB
small/40_simple_0011 WA 5 ms 12672 KB
small/40_simple_0012 WA 5 ms 12672 KB
small/40_simple_0013 WA 5 ms 12672 KB
small/40_simple_0014 WA 5 ms 12672 KB
small/40_simple_0015 WA 5 ms 12672 KB
small/40_simple_0016 WA 5 ms 12672 KB
small/40_simple_0017 WA 5 ms 12672 KB
small/40_simple_0018 WA 5 ms 12672 KB
small/40_simple_0019 WA 5 ms 12672 KB
small/90_dijkstra_killer_00 WA 5 ms 12672 KB
small/90_dijkstra_killer_01 WA 5 ms 12672 KB
small/91_tayama_killer_00 WA 5 ms 12672 KB
small/91_tayama_killer_01 WA 5 ms 12672 KB
small/91_tayama_killer_02 WA 5 ms 12672 KB
small/91_tayama_killer_03 WA 5 ms 12672 KB
small/91_tayama_killer_04 WA 5 ms 12672 KB
small/91_tayama_killer_05 WA 5 ms 12672 KB