Submission #1062958
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
#define INF INT_MAX/3
vector<vector<int> > d; // 隣接行列 適宜0とかINFとか
int n, m; // 頂点数
void warshall_floyd() {
rep (k, n) {
rep (i, n) {
rep (j, n) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
d.assign(n, vi(n, INF));
rep (i, n) {
d[i][i] = 0;
}
rep (i, m) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a -= 1; b -= 1;
d[a][b] = d[b][a] = c;
}
warshall_floyd();
ll s = 0;
rep (i, n) {
FOR (j, i+1, n) {
s += d[i][j];
}
}
int k;
scanf("%d", &k);
rep (query, k) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
x -= 1; y -= 1;
if (x > y) {
swap(x, y);
}
if (d[x][y] <= z) {
printf("%lld\n", s);
continue;
}
s = s - d[x][y] + z;
d[x][y] = d[y][x] = z;
rep (i, n) {
FOR (j, i+1, n) {
int new_cost = d[i][j];
new_cost = min(new_cost, d[i][x] + d[x][y] + d[y][j]);
new_cost = min(new_cost, d[i][y] + d[y][x] + d[x][j]);
if (new_cost < d[i][j]) {
s = s - d[i][j] + new_cost;
d[i][j] = d[j][i] = new_cost;
}
}
}
printf("%lld\n", s);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - アットコーダー王国の交通事情 |
User |
tspcx |
Language |
C++14 (Clang++ 3.4) |
Score |
100 |
Code Size |
2202 Byte |
Status |
AC |
Exec Time |
223 ms |
Memory |
1604 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 |
18 ms |
924 KB |
subtask0_sample_02.txt |
AC |
17 ms |
924 KB |
subtask1_01.txt |
AC |
19 ms |
920 KB |
subtask1_02.txt |
AC |
223 ms |
1564 KB |
subtask1_03.txt |
AC |
210 ms |
1560 KB |
subtask1_04.txt |
AC |
198 ms |
1560 KB |
subtask1_05.txt |
AC |
195 ms |
1560 KB |
subtask1_06.txt |
AC |
198 ms |
1560 KB |
subtask1_07.txt |
AC |
192 ms |
1604 KB |
subtask1_08.txt |
AC |
198 ms |
1564 KB |
subtask1_09.txt |
AC |
202 ms |
1560 KB |
subtask1_10.txt |
AC |
198 ms |
1560 KB |
subtask1_11.txt |
AC |
203 ms |
1560 KB |
subtask1_12.txt |
AC |
197 ms |
1556 KB |
subtask1_13.txt |
AC |
197 ms |
1564 KB |
subtask1_14.txt |
AC |
198 ms |
1564 KB |
subtask1_15.txt |
AC |
199 ms |
1564 KB |
subtask1_16.txt |
AC |
198 ms |
1560 KB |
subtask1_17.txt |
AC |
198 ms |
1564 KB |
subtask1_18.txt |
AC |
201 ms |
1564 KB |
subtask1_19.txt |
AC |
196 ms |
1556 KB |
subtask1_20.txt |
AC |
199 ms |
1556 KB |
subtask1_21.txt |
AC |
200 ms |
1560 KB |
subtask1_22.txt |
AC |
198 ms |
1564 KB |
subtask1_23.txt |
AC |
198 ms |
1560 KB |
subtask1_24.txt |
AC |
19 ms |
920 KB |
subtask1_25.txt |
AC |
19 ms |
920 KB |
subtask1_26.txt |
AC |
19 ms |
928 KB |
subtask1_27.txt |
AC |
19 ms |
924 KB |
subtask1_28.txt |
AC |
20 ms |
920 KB |
subtask1_29.txt |
AC |
17 ms |
924 KB |