結果
| 問題 | No.1320 Two Type Min Cost Cycle |
| ユーザー |
 manta1130
|
| 提出日時 | 2020-12-18 22:32:09 |
| 言語 | Rust (1.77.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,820 bytes |
| コンパイル時間 | 1,676 ms |
| コンパイル使用メモリ | 190,220 KB |
| 実行使用メモリ | 4,348 KB |
| 最終ジャッジ日時 | 2023-10-21 08:26:07 |
| 合計ジャッジ時間 | 6,147 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,348 KB |
| testcase_01 | AC | 0 ms
4,348 KB |
| testcase_02 | AC | 1 ms
4,348 KB |
| testcase_03 | AC | 1 ms
4,348 KB |
| testcase_04 | AC | 1 ms
4,348 KB |
| testcase_05 | AC | 1 ms
4,348 KB |
| testcase_06 | AC | 1 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,348 KB |
| testcase_08 | AC | 2 ms
4,348 KB |
| testcase_09 | TLE | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
コンパイルメッセージ
warning: unused attribute `macro_export`
--> Main.rs:130:5
|
130 | #[macro_export]
| ^^^^^^^^^^^^^^^
|
note: the built-in attribute `macro_export` will be ignored, since it's applied to the macro invocation `thread_local`
--> Main.rs:131:5
|
131 | thread_local! {
| ^^^^^^^^^^^^
= note: `#[warn(unused_attributes)]` on by default
warning: unused variable: `i`
--> Main.rs:7:9
|
7 | for i in 0..m {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: 2 warnings emitted
ソースコード
fn main() {
inputv! {
t:usize,
n:usize,m:usize,
}
let mut graph = vec![vec![]; n];
for i in 0..m {
inputv! {
u:usize,v:usize,w:isize
}
graph[u - 1].push((v - 1, w));
if t == 0 {
graph[v - 1].push((u - 1, w));
}
}
let mut ans = isize::max_value();
for i in 0..n {
let r = dijkstra(&graph, i);
ans = std::cmp::min(ans, r[i]);
//dbg!(r);
}
println!("{}", if ans == isize::max_value() { -1 } else { ans });
}
//https://github.com/manta1130/competitive-template-rs
use graph::*;
use input::*;
pub mod graph {
use std::cmp;
use std::collections::BinaryHeap;
#[allow(clippy::ptr_arg)]
pub fn bellman_ford(graph: &Vec<Vec<(usize, isize)>>, dist: &mut [Option<isize>]) -> Vec<bool> {
let mut neg_flag = vec![false; dist.len()];
for _ in 0..graph.len() {
for (from, v) in graph.iter().enumerate() {
for e in v.iter() {
let cost = e.1;
let to = e.0;
if let Some(x) = dist[from] {
if dist[to].is_none() {
dist[to] = Some(x + cost);
} else if let Some(y) = dist[to] {
if y > x + cost {
dist[to] = Some(x + cost);
}
}
}
}
}
}
for _ in 0..graph.len() {
for (from, v) in graph.iter().enumerate() {
for e in v.iter() {
let cost = e.1;
let to = e.0;
if let Some(x) = dist[from] {
if dist[to].is_none() {
dist[to] = Some(x + cost);
neg_flag[to] = true;
} else if let Some(y) = dist[to] {
if y > x + cost {
dist[to] = Some(x + cost);
neg_flag[to] = true;
}
}
}
if neg_flag[from] {
neg_flag[to] = true;
}
}
}
}
neg_flag
}
#[allow(clippy::ptr_arg)]
pub fn dijkstra(graph: &Vec<Vec<(usize, isize)>>, start: usize) -> Vec<isize> {
let mut heap = BinaryHeap::new();
let mut dist = vec![isize::max_value(); graph.len()];
dist[start] = 0;
heap.push((0_isize, start, start));
let mut first = true;
while !heap.is_empty() {
let e = heap.pop().unwrap();
if !first && e.1 == start {
return dist;
}
if dist[e.1] != -1 * e.0 {
continue;
}
for next_e in graph[e.1].iter() {
if e.2 != next_e.0 {
dist[next_e.0] = next_e.1 + dist[e.1];
heap.push(((dist[e.1] + next_e.1).wrapping_neg(), next_e.0, e.1));
}
}
if first && start == e.1 {
dist[start] = isize::max_value();
first = false;
}
}
dist
}
pub fn warshall_floyd(graph: &mut [&mut [isize]]) {
for k in 0..graph.len() {
for i in 0..graph.len() {
for j in 0..graph.len() {
graph[i][j] = cmp::min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
}
pub mod input {
use std::cell::RefCell;
use std::io;
pub const SPLIT_DELIMITER: char = ' ';
pub use std::io::prelude::*;
#[macro_export]
thread_local! {
pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
}
#[macro_export]
macro_rules! input_internal {
($x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let $x: $t = buf_split_result.parse().unwrap();
};
(mut $x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let mut $x: $t = buf_split_result.parse().unwrap();
};
}
#[macro_export]
macro_rules! inputv {
($i:ident : $t:ty) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty) => {
input_internal!{mut $i : $t}
};
($i:ident : $t:ty $(,)*) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty $(,)*) => {
input_internal!{mut $i : $t}
};
(mut $i:ident : $t:ty,$($q:tt)*) => {
input_internal!{mut $i : $t}
inputv!{$($q)*}
};
($i:ident : $t:ty,$($q:tt)*) => {
input_internal!{$i : $t}
inputv!{$($q)*}
};
}
pub fn input_all() {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let mut temp_str = String::new();
std::io::stdin().read_to_string(&mut temp_str).unwrap();
let mut split_result_iter = temp_str
.split_whitespace()
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
}
pub fn input_line_str() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).unwrap();
s.trim().to_string()
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector<T>() -> Vec<T>
where
T: std::str::FromStr,
{
let mut v: Vec<T> = Vec::new();
let s = input_line_str();
let split_result = s.split(SPLIT_DELIMITER);
for z in split_result {
let buf = match z.parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector_row<T>(n: usize) -> Vec<T>
where
T: std::str::FromStr,
{
let mut v = Vec::with_capacity(n);
for _ in 0..n {
let buf = match input_line_str().parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
pub trait ToCharVec {
fn to_charvec(&self) -> Vec<char>;
}
impl ToCharVec for String {
fn to_charvec(&self) -> Vec<char> {
self.to_string().chars().collect::<Vec<_>>()
}
}
}