Submission #1694715
Source Code Expand
fn main() {
let (n, m): (usize, usize) = get::read_tuple();
let edges: Vec<(usize, usize, isize)> = get::read_3tuples(m);
let edges = edges.iter().map(|&(a,b,c)|(a-1,b-1,-c)).collect::<Vec<_>>();
let g = Graph::new_labeled(n, &edges);
let dist = g.bellman_ford(0);
println!("{}", -dist[n-1])
}
struct Graph {
size: usize,
adj: Vec<Vec<(usize,isize)>>
}
impl Clone for Graph {
fn clone(&self) -> Graph {
Graph {
size: self.size,
adj: self.adj.clone()
}
}
}
#[allow(dead_code)]
impl Graph {
fn new_nonlabeled(n: usize, edges: &[(usize,usize)]) -> Graph {
let edges = edges.iter().map(|&(a,b)|(a,b,0isize)).collect::<Vec<_>>();
Graph::new_labeled(n, &edges)
}
fn new_labeled(n: usize, edges: &[(usize,usize,isize)]) -> Graph {
let mut g: Vec<Vec<(usize,isize)>> = vec![vec![]; n];
for &(a, b, c) in edges {
g[a].push((b,c));
}
Graph {size: n, adj: g}
}
fn is_connected(&self) -> bool {
self.dfs(0).len() == self.size
}
fn size(&self) -> usize {
self.size
}
fn edges_in(&self, v: usize) -> Vec<(usize, isize)> {
let mut buf = vec![];
for (i, next) in self.adj.iter().enumerate() {
for &(j, x) in next {
if j == v {buf.push((i, x))}
}
}
buf
}
fn bellman_ford(&self, s: usize) -> Vec<isize> {
let inf = isize::max_value() >> 1;
let mut bf: Vec<isize> = vec![inf; self.size];
bf[s] = 0;
for _ in 1 .. self.size {
for i in 0 .. self.size {
let es = self.edges_in(i);
let cand = es.iter().map(|&(v,c)|bf[v]+c).min().unwrap_or(inf);
bf[i] = std::cmp::min(bf[i], cand);
}
}
bf
}
fn bellman_ford2(&self, s: usize) -> Vec<isize> {
let inf = isize::max_value() >> 1;
let mut bf: Vec<isize> = vec![inf; self.size];
bf[s] = 0;
for _ in 1 .. self.size*2 {
for i in 0 .. self.size {
let es = self.edges_in(i);
let cand = es.iter().map(|&(v,c)|bf[v]+c).min().unwrap_or(inf);
bf[i] = std::cmp::min(bf[i], cand);
}
}
bf
}
fn dijkstra(&self, s: usize) -> Vec<isize> {
use std::collections::BinaryHeap;
let inf = isize::max_value();
let mut dk: Vec<isize> = vec![inf; self.size];
dk[s] = 0;
let mut pq = BinaryHeap::new();
pq.push((0,s));
while let Some((acc,v)) = pq.pop() {
let acc = -acc;
for &(w,c) in &self.adj[v] {
let cand = acc + c;
if cand < dk[w] {
dk[w] = cand;
pq.push((-cand,w));
}
}
}
dk
}
fn warshall_floyd(&self) -> Vec<Vec<isize>> {
let inf = isize::max_value() >> 1;
let mut wf: Vec<Vec<isize>> = vec![vec![inf; self.size]; self.size];
for i in 0 .. self.size {wf[i][i] = 0}
for (i, next) in self.adj.iter().enumerate() {
for &(j, x) in next {
wf[i][j] = x
}
}
for k in 0 .. self.size {
for i in 0 .. self.size {
for j in 0 .. self.size {
wf[i][j] = std::cmp::min(wf[i][j], wf[i][k] + wf[k][j]);
}
}
}
wf
}
fn coloring2(&self) -> Option<(Vec<usize>, Vec<usize>)> {
fn paint(v: usize, p: bool, g: &Graph, cv: &mut Vec<Option<bool>>) -> bool {
match cv[v] {
None => {
let next = &g.adj[v];
cv[v] = Some(p);
next.iter().all(|&(w,_)|paint(w,!p,g,cv))},
Some(q) => {q == p}
}
}
let mut canvas: Vec<Option<bool>> = vec![None; self.size];
let ans = paint(0, false, self, &mut canvas);
let bs = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(false)).map(|(i,_)|i).collect::<Vec<_>>();
let ws = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(true)).map(|(i,_)|i).collect::<Vec<_>>();
if ans {Some((bs,ws))} else {None}
}
fn dfs(&self, s: usize) -> Vec<usize> {
fn go(g: &Graph, current: usize, mut path: &mut Vec<usize>, mut visited: &mut Vec<bool>) {
for &(next, _) in &g.adj[current] {
if visited[next] {
continue
} else {
visited[next] = true;
path.push(next);
go(&g, next, &mut path, &mut visited)
}
}
}
let mut path = vec![s];
let mut visited = vec![false; self.adj.len()];
visited[s] = true;
go(&self, s, &mut path, &mut visited);
path
}
fn cut(&mut self, v: usize, w: usize) {
self.adj[v].retain(|&(t,_)| t != w);
self.adj[w].retain(|&(t,_)| t != v);
}
}
#[allow(dead_code)]
mod get {
use std::io::*;
use std::str::*;
pub fn read<T: FromStr>() -> T {
let mut buf = String::new();
stdin().read_line(&mut buf).ok();
buf.trim().parse::<T>().ok().unwrap()
}
pub fn reads<T: FromStr>(n: usize) -> Vec<T> {
let mut vec: Vec<T> = vec![];
for _ in 0 .. n {
vec.push(read());
}
vec
}
pub fn read_tuple<T1: FromStr, T2: FromStr>() -> (T1, T2) {
let mut buf = String::new();
stdin().read_line(&mut buf).ok();
let mut it = buf.trim().split_whitespace();
let x = it.next().unwrap().parse::<T1>().ok().unwrap();
let y = it.next().unwrap().parse::<T2>().ok().unwrap();
(x, y)
}
pub fn read_tuples<T1: FromStr, T2: FromStr>(n: usize) -> Vec<(T1, T2)> {
let mut vec: Vec<(T1, T2)> = vec![];
for _ in 0 .. n {
vec.push(read_tuple());
}
vec
}
pub fn read_3tuple<T1: FromStr, T2: FromStr, T3: FromStr>() -> (T1, T2, T3) {
let mut buf = String::new();
stdin().read_line(&mut buf).ok();
let mut it = buf.trim().split_whitespace();
let x = it.next().unwrap().parse::<T1>().ok().unwrap();
let y = it.next().unwrap().parse::<T2>().ok().unwrap();
let z = it.next().unwrap().parse::<T3>().ok().unwrap();
(x, y, z)
}
pub fn read_3tuples<T1: FromStr, T2: FromStr, T3: FromStr>(n: usize) -> Vec<(T1, T2, T3)> {
let mut vec: Vec<(T1, T2, T3)> = vec![];
for _ in 0 .. n {
vec.push(read_3tuple());
}
vec
}
pub fn read_vec<T: FromStr>() -> Vec<T> {
let mut buf = String::new();
stdin().read_line(&mut buf).ok();
buf.trim().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect()
}
pub fn read_mat<T: FromStr>(h: usize) -> Vec<Vec<T>> {
let mut mat: Vec<Vec<T>> = vec![];
for _ in 0 .. h {
mat.push(read_vec());
}
mat
}
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
aimy |
Language |
Rust (1.15.1) |
Score |
0 |
Code Size |
6555 Byte |
Status |
WA |
Exec Time |
2107 ms |
Memory |
4476 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
4352 KB |
sample_02.txt |
WA |
2 ms |
4352 KB |
sample_03.txt |
AC |
2 ms |
4352 KB |
subtask_1_1.txt |
AC |
146 ms |
4352 KB |
subtask_1_10.txt |
WA |
2 ms |
4352 KB |
subtask_1_11.txt |
WA |
114 ms |
4352 KB |
subtask_1_12.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_13.txt |
AC |
821 ms |
4352 KB |
subtask_1_14.txt |
TLE |
2107 ms |
4352 KB |
subtask_1_15.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_16.txt |
AC |
2 ms |
4352 KB |
subtask_1_17.txt |
AC |
4 ms |
4352 KB |
subtask_1_18.txt |
AC |
928 ms |
4352 KB |
subtask_1_19.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_2.txt |
AC |
1730 ms |
4352 KB |
subtask_1_20.txt |
AC |
953 ms |
4352 KB |
subtask_1_21.txt |
AC |
1804 ms |
4352 KB |
subtask_1_22.txt |
TLE |
2103 ms |
4352 KB |
subtask_1_23.txt |
AC |
2 ms |
4352 KB |
subtask_1_24.txt |
AC |
1964 ms |
4352 KB |
subtask_1_25.txt |
AC |
268 ms |
4352 KB |
subtask_1_26.txt |
AC |
1694 ms |
4352 KB |
subtask_1_27.txt |
AC |
1692 ms |
4352 KB |
subtask_1_3.txt |
AC |
799 ms |
4476 KB |
subtask_1_4.txt |
AC |
1741 ms |
4352 KB |
subtask_1_5.txt |
WA |
352 ms |
4352 KB |
subtask_1_6.txt |
WA |
1738 ms |
4352 KB |
subtask_1_7.txt |
AC |
1423 ms |
4352 KB |
subtask_1_8.txt |
AC |
1748 ms |
4352 KB |
subtask_1_9.txt |
AC |
2 ms |
4352 KB |