Submission #1680277
Source Code Expand
import java.util.Scanner import scala.collection.mutable.ListBuffer object Main { def dijkstra(G:Array[Array[Int]], s:Int): Int ={ val N = G.length val new_G = G.clone() val cand = new ListBuffer[Int]() for(i <- 0 until N){ if(i != s) cand.append(i) } while(cand.nonEmpty){ var point = -1 for(i <- cand){ if(point == -1) point = i else if(new_G(s)(i) <= new_G(s)(point)) point = i } cand.remove(cand.indexOf(point)) for(i <- cand) { if (new_G(s)(i) >= new_G(s)(point) + new_G(point)(i)) { new_G(s)(i) = new_G(s)(point) + new_G(point)(i) } } } return new_G(s).max } def main(args: Array[String]) = { val sc = new Scanner(System.in) val N = sc.nextInt val M = sc.nextInt val G = Array.fill(N, N)(1000 * 300) for(i <- 1 to M){ val a, b = sc.nextInt G(a - 1)(b - 1) = sc.nextInt G(b - 1)(a - 1) = G(a - 1)(b - 1) } for(i <- 0 until N){ G(i)(i) = 0 } val worst_time = new Array[Int](N) for(i <- 0 until N){ worst_time(i) = dijkstra(G, i) } println(worst_time.min) } }
Submission Info
Submission Time | |
---|---|
Task | D - バスと避けられない運命 |
User | macho_uno |
Language | Scala (2.11.7) |
Score | 100 |
Code Size | 1247 Byte |
Status | AC |
Exec Time | 1099 ms |
Memory | 67728 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 362 ms | 24140 KB |
sample_02.txt | AC | 336 ms | 25364 KB |
sample_03.txt | AC | 338 ms | 25412 KB |
test_01.txt | AC | 342 ms | 23632 KB |
test_02.txt | AC | 795 ms | 38832 KB |
test_03.txt | AC | 1099 ms | 67728 KB |
test_04.txt | AC | 793 ms | 36696 KB |
test_05.txt | AC | 904 ms | 44376 KB |
test_06.txt | AC | 687 ms | 34444 KB |
test_07.txt | AC | 999 ms | 49596 KB |
test_08.txt | AC | 416 ms | 27340 KB |
test_09.txt | AC | 845 ms | 51368 KB |
test_10.txt | AC | 664 ms | 34212 KB |
test_11.txt | AC | 702 ms | 36072 KB |
test_12.txt | AC | 888 ms | 39552 KB |
test_13.txt | AC | 697 ms | 36240 KB |
test_14.txt | AC | 731 ms | 38024 KB |
test_15.txt | AC | 966 ms | 50000 KB |
test_16.txt | AC | 733 ms | 39304 KB |
test_17.txt | AC | 854 ms | 42484 KB |
test_18.txt | AC | 860 ms | 40864 KB |
test_19.txt | AC | 766 ms | 39472 KB |
test_20.txt | AC | 709 ms | 38888 KB |
test_21.txt | AC | 345 ms | 25504 KB |
test_22.txt | AC | 791 ms | 38552 KB |
test_23.txt | AC | 403 ms | 25788 KB |
test_24.txt | AC | 789 ms | 38944 KB |
test_25.txt | AC | 803 ms | 38792 KB |
test_26.txt | AC | 620 ms | 35712 KB |
test_27.txt | AC | 645 ms | 37648 KB |
test_28.txt | AC | 776 ms | 38884 KB |
test_29.txt | AC | 804 ms | 39416 KB |
test_30.txt | AC | 520 ms | 31320 KB |
test_31.txt | AC | 395 ms | 26184 KB |
test_32.txt | AC | 768 ms | 38760 KB |
test_33.txt | AC | 799 ms | 38964 KB |
test_34.txt | AC | 457 ms | 28440 KB |
test_35.txt | AC | 604 ms | 35140 KB |
test_36.txt | AC | 786 ms | 39072 KB |