| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #66852 | #1327. [L3-2]不安定因子 | Accepted | 100 | 3265 ms | 2256 K | C++ 11 (NOI) / 1.2 K | Lrefrain | 2022-03-25 10:39:36 |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void read(int &x, int f = 1) {
x = 0;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-')
c = getchar(), f = -1;
while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
x *= f;
}
const int maxn = 5e2 + 5;
const ll INF = 1e18;
ll dis[maxn][maxn];
int n, m, d;
int main() {
read(n), read(m), read(d);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i ^ j)
dis[i][j] = INF;
for (int i = 1, x, y, z; i <= m; ++i) read(x), read(y), read(z), dis[x][y] = min(dis[x][y], (ll)z);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
for (int tim = 1, x, y, z, q; tim <= d; ++tim) {
read(x), read(y), read(z), read(q);
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k) dis[j][k] = min(dis[j][k], dis[j][x] + z + dis[y][k]);
for (int i = 1, x, y; i <= q; ++i) read(x), read(y), printf("%lld\n", dis[x][y]);
}
return 0;
}3 3 209
1 2 0
2 3 1
3 1 -2
2 1 2752
7
1 2
1 2
3 3
3 2
3 2
1 3
3 2
3 1 904
7
1 1
3 2
<10215 bytes omitted>-1
-1
-2
-3
-3
0
-3
-1
-3
-1
-1
-3
-3
-1
-3
-3
-3
0
-1
-1
-1
-1
-2
0
-2
-3
<5657 bytes omitted>用户输出
-1
-1
-2
-3
-3
0
-3
-1
-3
-1
-1
-3
-3
-1
-3
-3
-3
0
-1
-1
-1
-1
-2
0
-2
-3
-2
-3
-1
-1
-1
0
0
-2
-1
-1
-1
-3
-3
-3
-3
-3
-1
-3
-
<4107 bytes omitted>系统信息
Exited with return code 03 3 312
1 2 3
2 3 4
3 1 5
3 2 3432
1
2 2
1 1 2508
1
1 2
1 1 2692
1
2 3
2 1 3873
1
1 3
<5775 bytes omitted>0
3
4
7
3
0
9
5
3
3
9
9
7
5
3
9
4
7
3
7
0
8
0
0
0
3
4
8
0
7
5
4
4
0
<1007 bytes omitted>用户输出
0
3
4
7
3
0
9
5
3
3
9
9
7
5
3
9
4
7
3
7
0
8
0
0
0
3
4
8
0
7
5
4
4
0
8
3
0
9
0
8
0
0
8
9
9
0
5
0
5
0
0
5
8
0
3
0
0
9
8
3
5
5
0
0
<610 bytes omitted>系统信息
Exited with return code 0500 10000 209
70 305 46729
140 433 35103
454 442 51041
229 441 88672
311 435 42853
192 462 976
<170134 bytes omitted>43407
44894
69768
36741
32211
44504
32457
47251
52966
44619
18603
28778
44943
26079
36
<17656 bytes omitted>用户输出
43407
44894
69768
36741
32211
44504
32457
47251
52966
44619
18603
28778
44943
26079
36208
25370
34502
37001
22869
37006
9852
343
<15082 bytes omitted>系统信息
Exited with return code 0500 10000 269
326 187 29339
238 241 56713
15 178 12531
401 37 53317
466 45 10029
103 340 1311
<150446 bytes omitted>53793
30684
25103
24800
9908
30583
18631
41694
11426
27552
29474
16743
32061
17737
226
<1029 bytes omitted>用户输出
53793
30684
25103
24800
9908
30583
18631
41694
11426
27552
29474
16743
32061
17737
22640
39937
28862
23913
26939
37893
33204
391
<839 bytes omitted>系统信息
Exited with return code 0500 10000 357
430 227 -290
93 189 42205
173 316 80378
405 306 1852
447 337 73619
105 426 96732
<204660 bytes omitted>17703
44712
37931
35673
21537
24055
18024
17445
38327
29487
41441
32184
45824
52057
54
<43520 bytes omitted>用户输出
17703
44712
37931
35673
21537
24055
18024
17445
38327
29487
41441
32184
45824
52057
54764
20363
24231
32631
15216
36574
33346
32
<37216 bytes omitted>系统信息
Exited with return code 0500 10000 380
301 54 62658
351 342 53228
251 65 91564
30 51 53462
174 231 42410
376 380 98923
<226157 bytes omitted>30571
49765
23358
30559
26997
28611
33015
36079
37626
29958
6332
33021
28587
20312
169
<60650 bytes omitted>用户输出
30571
49765
23358
30559
26997
28611
33015
36079
37626
29958
6332
33021
28587
20312
16944
14317
28449
40334
26910
20699
30134
358
<51889 bytes omitted>系统信息
Exited with return code 0500 10000 68
388 326 21698
291 128 32903
332 471 75628
369 463 33908
275 392 54883
297 355 725
<199350 bytes omitted>16609
31927
26116
24961
27056
35219
19842
17744
38111
9895
15738
49371
47020
17308
188
<43495 bytes omitted>用户输出
16609
31927
26116
24961
27056
35219
19842
17744
38111
9895
15738
49371
47020
17308
18843
24760
27423
25941
22609
30167
20148
254
<37199 bytes omitted>系统信息
Exited with return code 0500 10000 384
199 140 32482
211 113 5376
281 296 28770
198 387 33129
39 281 44493
65 424 24306
<152577 bytes omitted>14614
14576
12735
28172
41786
31852
32979
15098
14821
33590
21456
18359
28230
33948
12
<1265 bytes omitted>用户输出
14614
14576
12735
28172
41786
31852
32979
15098
14821
33590
21456
18359
28230
33948
12137
20573
35585
20786
21550
17137
25936
20
<1040 bytes omitted>系统信息
Exited with return code 0500 300 40
62 155 -98
243 95 731
57 172 -474
35 226 776
41 233 728
416 459 371
350 264 393
2
<83404 bytes omitted>1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000
<192747 bytes omitted>用户输出
1000000000000000000
1000000000000000000
999999999999999017
1000000000000000000
1000000000000000000
1000000000000000000
100000000
<180017 bytes omitted>系统信息
Exited with return code 0500 300 165
481 84 72
143 447 110
289 167 -940
112 453 420
274 265 95
221 42 -712
471 362 280
<40196 bytes omitted>1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000
<81590 bytes omitted>用户输出
1000000000000000000
999999999999999494
999999999999999996
999999999999999221
1000000000000000000
1000000000000000000
10000000000
<75975 bytes omitted>系统信息
Exited with return code 0