Submission #1282043


Source Code Expand

Copy
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

macro_rules! trace {
    ($var:expr) => ({
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    })
}
macro_rules! swap { ($a:expr, $b:expr) => ({ let t = $b; $b = $a; $a = t; }) }

fn main() {
    let mut sc = Scanner::new();
    let n = sc.cin();
    let m = sc.cin();

    let mut neigh = vec![vec![]; n];
    let mut score = vec![vec![0 as i64; n]; n];

    for _ in 0..m {
        let a: usize = sc.cin();
        let b: usize = sc.cin();
        let c: i64 = sc.cin();
        neigh[a - 1].push(b - 1);
        score[a - 1][b - 1] = c;
    }

    let mut memo = vec![None; n];
    let mut visited = vec![0; n];
    { // Dijkstra
        memo[0] = Some(0);
        let mut stack = vec![0];
        while let Some(u) = stack.pop() {
            visited[u] += 1;

            if visited[u] > n * n + 1000 {
                println!("inf");
                return
            }

            for &v in neigh[u].iter() {
                if let Some(sc) = memo[v] {
                    let sc2 = memo[u].unwrap() + score[u][v];
                    if sc < sc2 {
                        memo[v] = Some(sc2);
                        stack.push(v);
                    }
                } else {
                    memo[v] = Some(memo[u].unwrap() + score[u][v]);
                    stack.push(v);
                }
            }
        }
    }

    println!("{}", memo[n - 1].unwrap());

}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
    fn get_char(&mut self) -> char {
        self.reserve();
        let head = self.buffer[0].chars().nth(0).unwrap();
        let tail = String::from( &self.buffer[0][1..] );
        if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.pop_front(); }
        head
    }
}

Submission Info

Submission Time
Task D - Score Attack
User cympfh
Language Rust (1.15.1)
Score 0
Code Size 2663 Byte
Status
Exec Time 2103 ms
Memory 535800 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 0 / 400 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 2 ms 4352 KB
sample_02.txt 2 ms 4352 KB
sample_03.txt 2 ms 4352 KB
subtask_1_1.txt 2 ms 4352 KB
subtask_1_10.txt 2 ms 4352 KB
subtask_1_11.txt 11 ms 11252 KB
subtask_1_12.txt 57 ms 40184 KB
subtask_1_13.txt 5 ms 12540 KB
subtask_1_14.txt 442 ms 77048 KB
subtask_1_15.txt 956 ms 535800 KB
subtask_1_16.txt 2 ms 4352 KB
subtask_1_17.txt 2 ms 4352 KB
subtask_1_18.txt 3 ms 6396 KB
subtask_1_19.txt 5 ms 10492 KB
subtask_1_2.txt 5 ms 12540 KB
subtask_1_20.txt 5 ms 12540 KB
subtask_1_21.txt 5 ms 12540 KB
subtask_1_22.txt 6 ms 12540 KB
subtask_1_23.txt 2 ms 4352 KB
subtask_1_24.txt 4 ms 8444 KB
subtask_1_25.txt 148 ms 4352 KB
subtask_1_26.txt 5 ms 12540 KB
subtask_1_27.txt 2103 ms 12540 KB
subtask_1_3.txt 4 ms 8444 KB
subtask_1_4.txt 5 ms 12540 KB
subtask_1_5.txt 1913 ms 6396 KB
subtask_1_6.txt 2103 ms 12540 KB
subtask_1_7.txt 4 ms 10492 KB
subtask_1_8.txt 5 ms 12540 KB
subtask_1_9.txt 2 ms 4352 KB