Submission #618037


Source Code Expand

#include <bits/stdc++.h>
#include <alloca.h>
using namespace std;
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)

string itos(long long n){
	stringstream ss;
	ss << n;
	return ss.str();
}
template<class T> ostream& operator<<(ostream& os, const pair<T,T>& p)
{
	os << "(" << p.first << "," << p.second << ")";
    return os;
}
template<class T> ostream& operator<<(ostream& os, const vector<T>& arr)
{
	os << "{";
	for(int i = 0 ; i < arr.size() ; i++) os << (i==0?"":",") << arr[i];
	os << "}";
    return os;
}
template<class T,int X> ostream& operator<<(ostream& os, const array<T,X> & arr)
{
	os << "{";
	for(int i = 0 ; i < arr.size() ; i++) os << (i==0?"":",") << arr[i];
	os << "}";
    return os;
}

#define int long long


struct Node{
	int a,b,c1,c2,c3;
};
vector<Node> g[30000];
vector<Node> rg[30000];
bool operator < (const Node &a,const Node &b){
	return a.c1 > b.c1;
}
// > w[j], w[j] += w[j-1];
		// for(int j = 1 ; j < L ; j++){
			// g[id[j-1]].push_back({id[j-1],id[j],w[j]-w[j-1],2*(w[L-1]-w[j])});
			// g[id[j]].push_back({id[j],id[j-1],w[j]-w[j-1],2*w[j-1]});
		// }

int sd[30000];

signed main(){
	for(int i = 0 ; i < 30000 ; i++)
		sd[i] = 1e18;
		
	int N,M,src,dst;
	cin >> N >> M >> src >> dst;
	for(int i = 0 ; i < M ; i++){
		int L;
		cin >> L;
		vector<int> id(L);
		vector<int> w(L);
		for(int j = 0 ; j < L ; j++) cin >> id[j];
		int tot = 0;
		w[0] = 0;
		for(int j = 1 ; j < L ; j++) cin >> w[j], w[j] += w[j-1];
		for(int j = 1 ; j < L ; j++){
			g[id[j-1]].push_back({id[j-1],id[j],w[j]-w[j-1],id[L-1],w[L-1]-w[j]});
			g[id[j]].push_back({id[j],id[j-1],w[j]-w[j-1],id[0],w[j-1]});
		}
	}
	for(int i = 0 ; i < N ; i++){
		for( auto e : g[i] ){
			swap(e.a,e.b);
			rg[e.a].push_back(e);
		}
	}
	
	{
		map<int,int> cost[30000];
		priority_queue<Node> Q;
		Q.push({dst,-1,0,0});

		while( Q.size() ){
			Node q = Q.top(); Q.pop();
			if( cost[q.a][q.c2] != q.c1 ) continue;
			sd[q.a] = q.c1;
			for( auto e : rg[q.a] ){
				Node nq = {e.b,-1,q.c1+e.c1,0};
				if( cost[nq.a].count(nq.c2) == 0 || cost[nq.a][nq.c2] > nq.c1 ){
					cost[nq.a][nq.c2]= nq.c1;
					Q.push(nq);
				}
			}
		}
	}
	{
		map<int,int> cost[30000];
		priority_queue<Node> Q;
		Q.push({src,-1,0,0});

		int ans = 1e9;
		while( Q.size() ){
			Node q = Q.top(); Q.pop();
			if( cost[q.a][q.c2] != q.c1 ) continue;
			if( q.a == dst ){
				ans = min(max(q.c1,q.c2),ans);
				continue;
			}
			for( auto e : g[q.a] ){
				Node nq = {e.b,-1,q.c1+e.c1,max(q.c2,sd[e.c2] + e.c1 + e.c3 + q.c1)};
				
				if( cost[nq.a].size() ){
					auto it = cost[nq.a].upper_bound(nq.c2);
					if( it != cost[nq.a].begin() ){
						--it;						
						if( it->second <= nq.c1 ) continue;
					}
				}
				
				if( cost[nq.a].count(nq.c2) == 0 || cost[nq.a][nq.c2] > nq.c1 ){
					cost[nq.a][nq.c2]= nq.c1;
					Q.push(nq);
				}
			}
		}
		cout << ans << endl;
	}
	
	
}

Submission Info

Submission Time
Task C - メンテナンス明け
User kyuridenamida
Language C++11 (GCC 4.9.2)
Score 100
Code Size 2989 Byte
Status AC
Exec Time 898 ms
Memory 36740 KB

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 898 ms 36740 KB
large/20_large-01 AC 540 ms 28948 KB
large/20_large-02 AC 198 ms 16788 KB
large/20_large-03 AC 323 ms 23448 KB
large/20_large-04 AC 463 ms 27408 KB
large/31_max_large AC 80 ms 10136 KB
small/00_sample00 AC 31 ms 3740 KB
small/00_sample01 AC 32 ms 3748 KB
small/00_sample02 AC 32 ms 3748 KB
small/10_small-0000 AC 34 ms 4000 KB
small/10_small-0001 AC 34 ms 3872 KB
small/10_small-0002 AC 34 ms 4004 KB
small/10_small-0003 AC 34 ms 4000 KB
small/10_small-0004 AC 34 ms 4008 KB
small/10_small-0005 AC 36 ms 4120 KB
small/10_small-0006 AC 35 ms 4000 KB
small/10_small-0007 AC 32 ms 3992 KB
small/10_small-0008 AC 32 ms 3868 KB
small/10_small-0009 AC 30 ms 3876 KB
small/10_small-0010 AC 29 ms 4004 KB
small/10_small-0011 AC 32 ms 4000 KB
small/10_small-0012 AC 32 ms 3988 KB
small/10_small-0013 AC 30 ms 4120 KB
small/10_small-0014 AC 30 ms 4004 KB
small/10_small-0015 AC 34 ms 4020 KB
small/10_small-0016 AC 33 ms 3996 KB
small/10_small-0017 AC 34 ms 3892 KB
small/10_small-0018 AC 31 ms 3868 KB
small/10_small-0019 AC 32 ms 3992 KB
small/30_max_small AC 31 ms 3880 KB
small/40_simple_0000 AC 30 ms 3748 KB
small/40_simple_0001 AC 29 ms 3756 KB
small/40_simple_0002 AC 30 ms 3752 KB
small/40_simple_0003 AC 32 ms 3800 KB
small/40_simple_0004 AC 29 ms 3828 KB
small/40_simple_0005 AC 32 ms 3740 KB
small/40_simple_0006 AC 29 ms 3744 KB
small/40_simple_0007 AC 31 ms 3744 KB
small/40_simple_0008 AC 29 ms 3752 KB
small/40_simple_0009 AC 32 ms 3740 KB
small/40_simple_0010 AC 32 ms 3756 KB
small/40_simple_0011 AC 32 ms 3744 KB
small/40_simple_0012 AC 32 ms 3744 KB
small/40_simple_0013 AC 30 ms 3748 KB
small/40_simple_0014 AC 34 ms 3752 KB
small/40_simple_0015 AC 32 ms 3752 KB
small/40_simple_0016 AC 35 ms 3824 KB
small/40_simple_0017 AC 33 ms 3744 KB
small/40_simple_0018 AC 32 ms 3756 KB
small/40_simple_0019 AC 34 ms 3748 KB
small/90_dijkstra_killer_00 AC 34 ms 3864 KB
small/90_dijkstra_killer_01 AC 31 ms 3864 KB
small/91_tayama_killer_00 AC 32 ms 3744 KB
small/91_tayama_killer_01 AC 32 ms 3744 KB
small/91_tayama_killer_02 AC 33 ms 3864 KB
small/91_tayama_killer_03 AC 32 ms 3748 KB
small/91_tayama_killer_04 AC 31 ms 3744 KB
small/91_tayama_killer_05 AC 32 ms 3748 KB