Submission #00007
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 | import java.io.*; import java.math.*; import java.util.*; class Main { private static final PrintWriter out = new PrintWriter(System.out); private static final Scanner scanner = new Scanner(System.in); private static int [] dx = {1, 0, -1, 0, 1, 1, -1, -1}; private static int [] dy = {0, 1, 0, -1, 1, -1, 1, -1}; private static int INF = 0x3f3f3f3f; private static long LINF = 0x3f3f3f3f3f3f3f3fL; private static long [] w = new long [100100]; private static long [] minCost = new long [100100]; private static List<Pair<Integer, Long>>[] graph = new ArrayList[100100]; private static PriorityQueue<Pair<Integer, Long>> priorityQueue = new PriorityQueue<>(Collections.reverseOrder()); public static void main(String[] args) { // From IntelliJ IDEA int n = fgetInt(); int m = fgetInt(); for ( int i = 1; i <= n; i++ ) { w[i] = fgetLong(); minCost[i] = LINF; graph[i] = new ArrayList<>(); } for ( int i = 0; i < m; i++ ) { int s = fgetInt(); int t = fgetInt(); long c = fgetLong(); graph[s].add( new Pair<>(t, c + w[s])); } priorityQueue.add( new Pair<>(1, 0L)); while ( !priorityQueue.isEmpty() ) { Pair<Integer, Long> now = priorityQueue.poll(); int pos = now.first; long cost = now.second; for ( Pair<Integer, Long> p : graph[pos] ) { int nextPos = p.first; long nextCost = cost + p.second; if ( nextCost < minCost[nextPos] ) { minCost[nextPos] = nextCost; priorityQueue.add( new Pair<>(nextPos, nextCost)); } } } if ( minCost[n] == LINF ) { println( "Whodunit" ); } else { println(minCost[n]); } suomi(); } private static boolean isMovable( int x, int y, int w, int h ) { return ( x >= 0 && y >= 0 && x < w && y < h ); } private static String fgetStr(){ return FastScanner.next(); } private static String fgetLine(){ return FastScanner.nextLine(); } private static char fgetChar(){ return fgetStr().charAt(0); } private static int fgetInt(){ return FastScanner.nextInt(); } private static long fgetLong(){ return FastScanner.nextLong(); } private static double fgetDouble(){ return FastScanner.nextDouble(); } private static BigInteger fgetBig(){ return new BigInteger(fgetStr()); } private static String reverseStr(String str){ return new StringBuffer(str).reverse().toString(); } private static void println(Object a){ out.println(a); } private static void print(Object a){ out.print(a); } private static void printf (String string, Object... args) { out. printf (string, args); } private static void suomi(){ out.flush(); } private static long pow ( long x, long n ) { final long MOD = 1000000007; long ans = 1; while ( n > 0 ) { if ( ( n & 1 ) == 1 ) { ans = (ans * x) % MOD; } x = ( x * x ) % MOD; n >>= 1; } return ans; } private static long gcd( long x, long y) { if ( y == 0 ) return x; return x % y == 0 ? y : gcd(y, x % y); } private static long lcm( long x, long y) { return ( x / gcd(x, y) * y); } } class Edge implements Comparable<Edge> { int u; int v; int cost; public Edge( int u, int v, int cost) { this .u = u; this .v = v; this .cost = cost; } @Override public int compareTo(Edge edge) { return Integer.compare( this .cost, edge.cost); } } class FastScanner { private static final InputStream in = System.in; private static final byte[] buffer = new byte[1024]; private static int ptr = 0; private static int bufferLength = 0; private static boolean hasNextByte() { if (ptr < bufferLength) { return true ; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch ( IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false ; } } return true ; } private static int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar( int c) { return 33 <= c && c <= 126; } private static boolean hasNext() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte(); } static String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } static String nextLine() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b) || b == 32) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } static long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false ; int b = readByte(); if (b == '-' ) { minus = true ; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while ( true ){ if ( '0' <= b && b <= '9' ) { n *= 10; n += b - '0' ; } else if (b == -1 || !isPrintableChar(b)){ return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } static int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException(); return ( int ) nl; } static double nextDouble() { return Double.parseDouble(next()); } } class Pair<F, S> implements Comparable<Pair<F, S>> { F first; S second; public Pair(F a, S b) { this .first = a; this .second = b; } @Override public int compareTo(Pair<F, S> pair) { int firstCmp = Objects.compare( this .first, pair.first, Comparator.comparing(Object::toString)); if ( firstCmp == 0 ) { return Objects.compare( this .second, pair.second, Comparator.comparing(Object::toString)); } return firstCmp; } public boolean equals(Pair<F, S> pair) { return this .first.equals(pair.first) && this .second.equals(pair.second); } public String toString() { return String.valueOf(first) + ", " + String.valueOf(second); } } |
ステータス
項目 | データ |
---|---|
問題 | 0005 - 我々はどこから来たのか 我々は何者か 我々はどこへ行くのか |
ユーザー名 | r1825 |
投稿日時 | 2019-04-24 16:02:29 |
言語 | Java |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 7514 Byte |
最大実行時間 | 1149 ms |
最大メモリ使用量 | 48644 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
corner | AC | 148 ms | 20576 KB |
1
|
in01 | AC | 668 ms | 41220 KB |
1
|
in02 | AC | 745 ms | 43524 KB |
1
|
in03 | AC | 828 ms | 41176 KB |
1
|
in04 | AC | 702 ms | 41116 KB |
1
|
in05 | AC | 699 ms | 40992 KB |
1
|
in06 | AC | 876 ms | 43212 KB |
1
|
in07 | AC | 1048 ms | 48644 KB |
1
|
in08 | AC | 648 ms | 41164 KB |
1
|
in09 | AC | 837 ms | 42860 KB |
1
|
in10 | AC | 605 ms | 41144 KB |
1
|
in11 | AC | 831 ms | 43284 KB |
1
|
in12 | AC | 1149 ms | 43148 KB |
1
|
in13 | AC | 790 ms | 39040 KB |
1
|
in14 | AC | 686 ms | 41112 KB |
1
|
in15 | AC | 816 ms | 41176 KB |
1
|
in16 | AC | 688 ms | 40996 KB |
1
|
in17 | AC | 718 ms | 42872 KB |
1
|
in18 | AC | 723 ms | 41324 KB |
1
|
in19 | AC | 696 ms | 41220 KB |
1
|
in20 | AC | 628 ms | 41060 KB |
1
|
unknown | AC | 124 ms | 16712 KB |
1
|