Submission #352345
Source Code Expand
#include <iostream> using namespace std; int N, M; int d[420][420]; int K; int main() { while (cin >> N >> M) { for (int i = 0; i <= 401; i++) { for (int j = 0; j <= 401; j++) { d[i][j] = 1<<28; } d[i][i] = 0; } for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; --a; --b; d[a][b] = d[b][a] = c; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } cin >> K; while (K--) { int x, y, z; cin>>x>>y>>z; --x; --y; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][x] + z + d[y][j]); d[i][j] = min(d[i][j], d[i][y] + z + d[x][j]); } } long long s = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { s += d[i][j]; } } cout << s << endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - アットコーダー王国の交通事情 |
User | brly |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1178 Byte |
Status | AC |
Exec Time | 435 ms |
Memory | 1592 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 10 / 10 | 90 / 90 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt |
Subtask1 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 24 ms | 1568 KB |
subtask0_sample_02.txt | AC | 24 ms | 1444 KB |
subtask1_01.txt | AC | 25 ms | 1448 KB |
subtask1_02.txt | AC | 423 ms | 1564 KB |
subtask1_03.txt | AC | 420 ms | 1436 KB |
subtask1_04.txt | AC | 424 ms | 1440 KB |
subtask1_05.txt | AC | 414 ms | 1440 KB |
subtask1_06.txt | AC | 421 ms | 1560 KB |
subtask1_07.txt | AC | 435 ms | 1444 KB |
subtask1_08.txt | AC | 425 ms | 1448 KB |
subtask1_09.txt | AC | 431 ms | 1564 KB |
subtask1_10.txt | AC | 420 ms | 1384 KB |
subtask1_11.txt | AC | 429 ms | 1568 KB |
subtask1_12.txt | AC | 424 ms | 1448 KB |
subtask1_13.txt | AC | 424 ms | 1440 KB |
subtask1_14.txt | AC | 413 ms | 1564 KB |
subtask1_15.txt | AC | 418 ms | 1592 KB |
subtask1_16.txt | AC | 416 ms | 1560 KB |
subtask1_17.txt | AC | 417 ms | 1568 KB |
subtask1_18.txt | AC | 413 ms | 1448 KB |
subtask1_19.txt | AC | 417 ms | 1436 KB |
subtask1_20.txt | AC | 416 ms | 1440 KB |
subtask1_21.txt | AC | 415 ms | 1444 KB |
subtask1_22.txt | AC | 416 ms | 1556 KB |
subtask1_23.txt | AC | 414 ms | 1568 KB |
subtask1_24.txt | AC | 31 ms | 1444 KB |
subtask1_25.txt | AC | 31 ms | 1568 KB |
subtask1_26.txt | AC | 31 ms | 1436 KB |
subtask1_27.txt | AC | 30 ms | 1564 KB |
subtask1_28.txt | AC | 29 ms | 1564 KB |
subtask1_29.txt | AC | 28 ms | 1572 KB |