XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#20870 #1066. 1-08E. cty的等式与不等式 Accepted 100 1460 ms 2344 K C++ / 982 B kong 2019-08-14 10:42:19
显示原始代码 
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAX = 505;
int graph[MAX][MAX];
int dist[MAX][MAX];

inline void add(int u, int v, int m) { graph[u][v] = min(m, graph[u][v]); }

void floyd(int n) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) dist[i][j] = graph[i][j];
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    for (int k = 1; k <= n; k++)
        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= n; i++) {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
}

int main() {
    int n, m, q;
    while (scanf("%d%d%d", &n, &m, &q) != EOF) {
        memset(graph, INF, sizeof(graph));
        int k, a, b, c;
        while (m--) {
            scanf("%d%d%d%d", &k, &a, &b, &c);
            if (k == 1)
                add(b, a, c);
            if (k == 2) {
                add(b, a, c);
                add(a, b, -c);
            }
            if (k == 3)
                add(a, b, -c);
        }
        floyd(n);
        while (q--) {
            scanf("%d%d", &a, &b);
            printf("%d\n", dist[b][a]);
        }
    }
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：6 ms
内存：1300 KiB

输入文件（1.in） 

3 3 2
1 1 2 0
1 2 3 1
3 3 1 2
1 2
1 3

答案文件（1.out） 

0
-2

用户输出 

0
-2

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：5 ms
内存：1284 KiB

输入文件（2.in） 

3 3 2
1 1 2 3
1 2 3 4
1 3 1 5
1 3
3 2

答案文件（2.out） 

7
8

用户输出 

7
8

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：194 ms
内存：2304 KiB

输入文件（3.in） 

500 10000 10000
3 70 305 -46729
3 140 433 -35103
1 454 442 51041
3 229 441 -88672
1 311 435 428
<255129 bytes omitted>

答案文件（3.out） 

31678
35216
17803
21098
46380
16022
20680
32989
25696
46600
17717
41253
30447
40350
37
<69678 bytes omitted>

用户输出 

31678
35216
17803
21098
46380
16022
20680
32989
25696
46600
17717
41253
30447
40350
37002
9251
38214
32357
49786
48186
48759
405
<59650 bytes omitted>

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：187 ms
内存：2300 KiB

输入文件（4.in） 

500 10000 10000
1 326 187 29339
3 238 241 -56713
3 15 178 -12531
3 401 37 -53317
1 466 45 10029
<255174 bytes omitted>

答案文件（4.out） 

50802
39980
25832
48758
39534
49421
26670
29367
31494
10036
42953
25597
42118
9655
300
<69734 bytes omitted>

用户输出 

50802
39980
25832
48758
39534
49421
26670
29367
31494
10036
42953
25597
42118
9655
30089
42814
43166
39745
32430
44494
18514
476
<59706 bytes omitted>

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：186 ms
内存：2280 KiB

输入文件（5.in） 

500 10000 10000
3 430 227 290
1 93 189 42205
3 173 316 -80378
3 405 306 -1852
3 447 337 -73619
<255044 bytes omitted>

答案文件（5.out） 

27683
34262
38877
48498
36602
47321
36405
24844
26650
40405
19085
17746
24275
46974
29
<69495 bytes omitted>

用户输出 

27683
34262
38877
48498
36602
47321
36405
24844
26650
40405
19085
17746
24275
46974
29174
26767
42604
35259
50451
20873
19468
22
<59467 bytes omitted>

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：185 ms
内存：2292 KiB

输入文件（6.in） 

500 10000 10000
1 301 54 62658
3 351 342 -53228
1 251 65 91564
1 30 51 53462
3 174 231 -42410

<255106 bytes omitted>

答案文件（6.out） 

28970
39668
22803
16060
41803
26369
54625
27575
8457
23438
34774
32152
34101
32600
389
<69430 bytes omitted>

用户输出 

28970
39668
22803
16060
41803
26369
54625
27575
8457
23438
34774
32152
34101
32600
38935
21431
36687
49707
41850
23171
13843
498
<59402 bytes omitted>

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：186 ms
内存：2284 KiB

输入文件（7.in） 

500 10000 10000
1 388 326 21698
1 291 128 32903
1 332 471 75628
1 369 463 33908
1 275 392 54883
<254889 bytes omitted>

答案文件（7.out） 

13611
25815
12684
9825
41239
36365
49633
29539
23599
34858
36284
17044
17247
31461
261
<69399 bytes omitted>

用户输出 

13611
25815
12684
9825
41239
36365
49633
29539
23599
34858
36284
17044
17247
31461
26123
42007
37324
57100
14740
5155
23495
2589
<59371 bytes omitted>

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：187 ms
内存：2268 KiB

输入文件（8.in） 

500 10000 10000
3 199 140 -32482
3 211 113 -5376
3 281 296 -28770
1 198 387 33129
3 39 281 -444
<254977 bytes omitted>

答案文件（8.out） 

36631
10751
24293
24559
25446
32762
43906
34447
30775
34872
0
40015
28093
12508
18270
<69460 bytes omitted>

用户输出 

36631
10751
24293
24559
25446
32762
43906
34447
30775
34872
0
40015
28093
12508
18270
27208
20682
17677
19306
34906
21891
43013

<59432 bytes omitted>

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：158 ms
内存：2340 KiB

输入文件（9.in） 

500 300 500
3 62 155 98
3 243 95 -731
1 57 172 -474
3 35 226 -776
3 41 233 -728
2 416 459 371
<8748 bytes omitted>

答案文件（9.out） 

-1049
-735
-53
-70
-133
-1199
513
-354
493
-1193
-216
-2211
532
0
993
0
-210
0
0

<2433 bytes omitted>

用户输出 

-1049
-735
-53
-70
-133
-1199
513
-354
493
-1193
-216
-2211
532
0
993
0
-210
0
0
-816
0
1995
328
-675
-1130
365
0
-843
-789
-368
<1905 bytes omitted>

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：166 ms
内存：2344 KiB

输入文件（10.in） 

500 300 500
2 481 84 -72
2 143 447 -110
3 289 167 940
2 112 453 420
1 274 265 95
3 221 42 712
<8771 bytes omitted>

答案文件（10.out） 

-1176
-586
-703
877
0
-3327
785
-1507
-3327
-988
-3213
-846
506
298
503
121
-1467
-
<2638 bytes omitted>

用户输出 

-1176
-586
-703
877
0
-3327
785
-1507
-3327
-988
-3213
-846
506
298
503
121
-1467
-1277
-553
-1382
-1536
-791
-549
-753
594
-582
<2110 bytes omitted>

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.