結果

問題 No.848 なかよし旅行
コンテスト
ユーザー chocorusk
提出日時 2020-05-08 08:41:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 133 ms / 2,000 ms
コード長 3,703 bytes
コンパイル時間 1,420 ms
コンパイル使用メモリ 125,544 KB
最終ジャッジ日時 2025-01-10 07:41:02
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
template<typename val_t, typename key_t>
struct FibonacciHeap{
	struct Node{
		val_t val;
		key_t key;
		int deg;
		Node *par, *ch, *l, *r;
		bool mark;
		Node(val_t val, key_t key):val(val), key(key), par(nullptr), ch(nullptr), l(this), r(this), mark(false), deg(0){}
	};
	vector<Node*> vr;
	Node *min_node;
	int sz;
	FibonacciHeap():sz(0), min_node(nullptr){}
	bool empty(){
		return sz==0;
	}
	void concat(Node *&s, Node *t){
		if(!t) return;
		if(!s){
			s=t;
			return;
		}
		s->r->l=t->l;
		t->l->r=s->r;
		s->r=t;
		t->l=s;
	}
	void delete_node(Node *t){
		t->l->r=t->r;
		t->r->l=t->l;
		t->l=t;
		t->r=t;
	}
	Node *push(val_t val, key_t key){
		sz++;
		Node *t=new Node(val, key);
		concat(min_node, t);
		if(!min_node || t->val<min_node->val) min_node=t;
		return t;
	}
	void link(Node *t, Node *c){
		t->deg++;
		delete_node(c);
		c->par=t;
		concat(c, t->ch);
		if(!t->ch) t->ch=c;
	}
	pair<val_t, key_t> pop(){
		sz--;
		pair<val_t, key_t> ret=make_pair(min_node->val, min_node->key);
		auto y=(min_node->r==min_node)?nullptr:min_node->r;
		delete_node(min_node);
		auto x=min_node->ch;
		if(x) x->par=nullptr;
		concat(x, y);
		min_node=nullptr;
		if(!x){
			return ret;
		}
		auto x1=x;
		do{
			x1->par=nullptr;
			if(!min_node || x1->val<min_node->val) min_node=x1;
			x1=x1->r;
		}while(x1!=x);
		x1=min_node;
		int last=-1;
		do{
			auto xr=x1->r;
			while(x1->deg<vr.size() && vr[x1->deg]){
				auto x2=vr[x1->deg];
				vr[x1->deg]=nullptr;
				if(x2==min_node || x1->val>x2->val){
					swap(x1, x2);
				}
				link(x1, x2);
			}
			if(x1->deg>=vr.size()) vr.resize(x1->deg+1);
			vr[x1->deg]=x1;
			last=max(last, x1->deg);
			x1=xr;
		}while(x1!=min_node);
		for(int i=0; i<=last; i++) vr[i]=nullptr;
		return ret;
	}
	void decrease(Node *t, val_t d){//t->val=d
		t->val=d;
		if(!t->par){
			if(!min_node || t->val<min_node->val) min_node=t;
			return;
		}
		if(t->par->val<=d) return;
		while(t->par){
			auto tp=t->par;
			t->par->deg--;
			t->par->ch=((t->r==t)?nullptr:t->r);
			delete_node(t);
			t->par=nullptr;
			concat(min_node, t);
			if(!min_node || t->val<min_node->val) min_node=t;
			if(!tp->mark){
				tp->mark=1;
				break;
			}
			t=tp;
		}
	}
};
const ll INF=1e16;
int n, m, p, q;
vector<P> g[2001];
void dijkstra(int s, ll d[2001]){
	fill(d, d+n, INF);
	d[s]=0;
	FibonacciHeap<ll, int> que;
	using node=FibonacciHeap<ll, int>::Node;
	vector<node*> v(n);
	v[s]=que.push(0, s);
	while(!que.empty()){
		auto p1=que.pop();
		int x=p1.second;
		for(int j=0; j<g[x].size(); j++){
			P q1=g[x][j];
			int y=q1.second;
			if(d[y]>d[x]+q1.first){
				d[y]=d[x]+q1.first;
				if(!v[y]) v[y]=que.push(d[y], y);
				else que.decrease(v[y], d[y]);
			}
		}
	}
}
int main()
{
	ll t;
	cin>>n>>m>>p>>q>>t; p--; q--;
	for(int i=0; i<n; i++) g[i].clear();
	for(int i=0; i<m; i++){
		int a, b; ll c; cin>>a>>b>>c; a--; b--;
		g[a].push_back(P(c, b));
		g[b].push_back(P(c, a));
	}
	ll d1[2001], dp[2001], dq[2001];
	dijkstra(0, d1);
	dijkstra(p, dp);
	dijkstra(q, dq);
	if(t<max(2*d1[p], 2*d1[q])){
		cout<<-1<<endl;
		return 0;
	}else if(t>=d1[p]+dp[q]+d1[q]){
		cout<<t<<endl;
		return 0;
	}
	ll ans=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ll dm=max(dp[i]+dp[j], dq[i]+dq[j]);
			if(dm+d1[i]+d1[j]>t) continue;
			ans=max(ans, t-dm);
		}
	}
	cout<<ans<<endl;
	return 0;
}
0