106 lines
2.6 KiB
Rust
106 lines
2.6 KiB
Rust
use std::{collections::BinaryHeap, io::stdin, usize};
|
|
|
|
#[derive(Eq, PartialEq)]
|
|
struct DistElem {
|
|
node: usize,
|
|
dist: usize,
|
|
}
|
|
|
|
impl Ord for DistElem {
|
|
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
|
|
self.dist.cmp(&other.dist)
|
|
}
|
|
}
|
|
|
|
impl PartialOrd for DistElem {
|
|
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
|
|
Some(self.cmp(other))
|
|
}
|
|
}
|
|
|
|
fn find_longest_by_reverse_dijkstra(
|
|
n: usize,
|
|
ways_by_city: &Vec<Vec<(usize, usize)>>,
|
|
start: usize,
|
|
end: usize,
|
|
) -> (usize, usize) {
|
|
let mut max_dist = vec![0; n];
|
|
let mut prev = vec![usize::MAX; n];
|
|
let mut heap: BinaryHeap<DistElem> = BinaryHeap::new();
|
|
|
|
heap.push(DistElem {
|
|
node: start,
|
|
dist: 0,
|
|
});
|
|
|
|
while !heap.is_empty() {
|
|
let DistElem { node, dist } = heap.pop().unwrap();
|
|
|
|
if dist < max_dist[node] {
|
|
continue;
|
|
}
|
|
|
|
for (v, w) in &ways_by_city[node] {
|
|
let next_dist = dist + w;
|
|
|
|
if next_dist > max_dist[*v] {
|
|
max_dist[*v] = next_dist;
|
|
prev[*v] = node;
|
|
heap.push(DistElem {
|
|
node: *v,
|
|
dist: next_dist,
|
|
});
|
|
}
|
|
}
|
|
}
|
|
|
|
let mut path_length = 0;
|
|
|
|
let mut curr = end;
|
|
while curr != start {
|
|
path_length += 1;
|
|
curr = prev[curr];
|
|
println!("curr: {}", curr);
|
|
}
|
|
(max_dist[end], path_length)
|
|
}
|
|
|
|
fn main() {
|
|
let mut line = String::new();
|
|
stdin().read_line(&mut line).unwrap();
|
|
let n: usize = line.trim().parse().unwrap();
|
|
line.clear();
|
|
stdin().read_line(&mut line).unwrap();
|
|
let m: usize = line.trim().parse().unwrap();
|
|
|
|
let mut ways_by_city: Vec<Vec<(usize, usize)>> = vec![vec![]; n];
|
|
|
|
for _ in 0..m {
|
|
line.clear();
|
|
stdin().read_line(&mut line).unwrap();
|
|
let mut iter = line
|
|
.trim()
|
|
.split(' ')
|
|
.map(|x| x.trim().parse::<usize>().unwrap());
|
|
let (u, v, w) = (
|
|
iter.next().unwrap() - 1, // convert to index
|
|
iter.next().unwrap() - 1, // convert to index
|
|
iter.next().unwrap(),
|
|
);
|
|
|
|
ways_by_city[u].push((v, w));
|
|
}
|
|
|
|
line.clear();
|
|
stdin().read_line(&mut line).unwrap();
|
|
let mut iter = line
|
|
.trim()
|
|
.split(' ')
|
|
.map(|x| x.trim().parse::<usize>().unwrap());
|
|
|
|
let (start, end) = (iter.next().unwrap() - 1, iter.next().unwrap() - 1);
|
|
|
|
let res = find_longest_by_reverse_dijkstra(n, &ways_by_city, start, end);
|
|
println!("{}\n{}", res.0, res.1);
|
|
}
|