結果

問題 No.848 なかよし旅行
コンテスト
ユーザー yoma
提出日時 2020-03-06 01:03:47
言語 Rust
(1.83.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,445 bytes
コンパイル時間 16,240 ms
コンパイル使用メモリ 377,420 KB
実行使用メモリ 14,976 KB
最終ジャッジ日時 2024-11-08 01:13:17
合計ジャッジ時間 20,152 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_macros)]
macro_rules! input {
	(source = $s:expr, $($r:tt)*) => {
		let mut iter = $s.split_whitespace();
		input_inner!{iter, $($r)*}
	};
	($($r:tt)*) => {
		let s = {
			use std::io::Read;
			let mut s = String::new();
			std::io::stdin().read_to_string(&mut s).unwrap();
			s
		};
		let mut iter = s.split_whitespace();
		input_inner!{iter, $($r)*}
	};
}
#[allow(unused_macros)]
macro_rules! input_inner {
	($iter:expr) => {};
	($iter:expr, ) => {};

	($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
		let $var = read_value!($iter, $t);
		input_inner!{$iter $($r)*}
	};
}
#[allow(unused_macros)]
macro_rules! read_value {
	($iter:expr, ( $($t:tt),* )) => {
		( $(read_value!($iter, $t)),* )
	};

	($iter:expr, [ $t:tt ; $len:expr ]) => {
		(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
	};

	($iter:expr, chars) => {
		read_value!($iter, String).chars().collect::<Vec<char>>()
	};

	($iter:expr, usize1) => {
		read_value!($iter, usize) - 1
	};

	($iter:expr, $t:ty) => {
		$iter.next().unwrap().parse::<$t>().expect("Parse error")
	};
}

use std::collections::BinaryHeap;

fn dijkstra(s: usize, d: &mut Vec<i64>, graph: &Vec<Vec<(i64, usize)>>) {
	for i in 0..d.len() { d[i] = 1000000000; }
	d[s] = 0;
	let mut que = BinaryHeap::new();
	que.push(s);
	while !que.is_empty() {
		let v1 = que.pop().unwrap();
		for e in &graph[v1] {
			let dis2 = e.0;
			let v2 = e.1;
			if d[v2] > d[v1] + dis2 {
				que.push(v2);
				d[v2] = d[v1] + dis2;
			}
		}
	}
}

fn main() {
	input!{
		n: usize,
		m: usize,
		p: usize,
		q: usize,
		t: i64,
		edges: [(usize1, usize1, i64); m],
	}
	let mut dp: Vec<i64> = vec![0; n];
	let mut dq: Vec<i64> = vec![0; n];
	let mut d0: Vec<i64> = vec![0; n];
	let mut graph: Vec<Vec<(i64, usize)>> = vec![vec![]; n];
	for edge in edges {
		let from = edge.0;
		let to = edge.1;
		let cost = edge.2;
		graph[from].push((cost, to));
		graph[to].push((cost, from));
	}
	let p = p-1;
	let q = q-1;
	dijkstra(p, &mut dp, &graph);
	dijkstra(q, &mut dq, &graph);
	dijkstra(0, &mut d0, &graph);
	let mut ans = -1;
	for i in 0..n {
		for j in 0..n {
			let rp = d0[i]+dp[i]+dp[j]+d0[j];
			let rq = d0[i]+dq[i]+dq[j]+d0[j];
			if rp <= t && rq <= t {
				let tt = t-std::cmp::max(dp[i]+dp[j], dq[i]+dq[j]);
				ans = std::cmp::max(ans, tt);
			}
		}
	}
	if d0[p]+dp[q]+d0[q] <= t {
		ans = t;
	}
	// println!("{:?}", dp);
	// println!("{:?}", dq);
	// println!("{:?}", d0);
	println!("{}", ans);
}
0