Submission #617506

---

Source Code Expand

#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int My_Inf=2147483647;
const long long int My_LInf=9223372036854775807;

struct edge {
	int from;
	int to;
	int fin;
	long long int fincost;
	long long int cost;
};
struct aa {
	bool slept;
	long long int time;
	int now;
};
class Compare {
public:
	//aaが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};

long long int perftime[30000];

int N, M, S, D;
bool check(long long int atime, const vector<vector<edge>>&edges) {
	priority_queue<aa, vector<aa>, Compare>que;
	que.push(aa{ false,0,S });

	long long int mintime[30000];
	for (int i = 0; i < 30000; ++i) {
			mintime[i] = My_LInf;
	}
	mintime[S] = 0;
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		int now = atop.now;
		if (atop.time >= atime)return false;
		for (auto e : edges[now]) {
			long long int  nexttime = atop.time + e.fincost;
			int nextplace = e.fin;

			if (atime< nexttime+perftime[nextplace]) {
			}
			else {
				long long int  nexttime = atop.time + e.cost;
				int nextplace = e.to;
				if (mintime[nextplace] > nexttime) {
					if (nextplace == D)return true;
					mintime[nextplace] = nexttime;
					que.push(aa{ false,nexttime,nextplace });
				}
			}
		}
		
	}
	return false;
}
int main() {
	for (int i = 0; i < 30000; ++i) {
		perftime[i] = My_LInf;
	}
cin >> N >> M >> S >> D;
	vector<vector<edge>>edges(N);
	for (int i = 0; i < M; ++i) {
		int L; cin >> L;
		vector<int>ss;
		for (int i = 0; i < L; ++i) {
			int s; cin >> s;
			ss.push_back(s);
		}
		vector<int>ws;
		vector<edge>aedges;
		int allsum = 0;
		for (int i = 0; i < L - 1; ++i) {
			int w; cin >> w;
			ws.push_back(w);
			allsum += w;
		}
		int nowsum = 0;
		for (int i = 0; i < L - 1; ++i) {
			edges[ss[i]].push_back(edge{ ss[i],ss[i + 1],ss[L - 1],allsum - nowsum,ws[i] });
			nowsum += ws[i];
			edges[ss[i+1]].push_back(edge{ ss[i+1],ss[i],ss[0],nowsum,ws[i] });
			
		}
	}

	{
		priority_queue<aa, vector<aa>, Compare>que;
		que.push(aa{ true,0,D });
		perftime[D] = 0;

		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			int now = atop.now;
			bool aslept = atop.slept;
			for (auto e : edges[now]) {
				long long int  nexttime = atop.time + e.cost;
				int nextplace = e.to;
				if (perftime[nextplace] > nexttime) {
					perftime[nextplace] = nexttime;
					que.push(aa{ aslept,nexttime,nextplace });
				}
			}
		}
	}

	{
		long long int amin = 0;
		long long int amax = My_LInf / 2;
		while (amin + 1 != amax) {
			long long int amid = (amin + amax) / 2;
			if (check(amid, edges)) {
				amax = amid;
			}
			else {
				amin = amid;
			}
		}
		long long int ans = amax;

		cout << amax << endl;

	}
	return 0;
}

Submission Info

Judge Result