XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#9536 #1066. 1-08E. cty的等式与不等式 Accepted 100 853 ms 1432 K C++ 11 / 1.3 K RBTsDefoliation 2019-07-03 8:28:24
显示原始代码 
#include <bits/stdc++.h>
#define MAXN 505
#define MAXM 10005
#define INF 1000000005

using namespace std;

struct Graph {
    int n, m;

    int to[MAXM << 1];
    int next[MAXM << 1];
    int w[MAXM << 1];
    int head[MAXN];

    int dist[MAXN][MAXN];

    void build(int size) { n = size; }

    void add(int u, int v, int weight) {
        to[++m] = v;
        next[m] = head[u];
        w[m] = weight;
        head[u] = m;
    }

    void floyd() {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) dist[i][j] = i == j ? 0 : INF;
        for (int i = 1; i <= n; ++i)
            for (int j = head[i]; j; j = next[j]) dist[i][to[j]] = min(dist[i][to[j]], w[j]);
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
};

Graph g;

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    g.build(n);
    int k, a, b, c;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d %d", &k, &a, &b, &c);
        if (k == 1)
            g.add(a, b, c);
        else if (k == 2) {
            g.add(a, b, c);
            g.add(b, a, -c);
        } else
            g.add(b, a, -c);
    }
    g.floyd();
    for (int i = 0; i < q; ++i) {
        scanf("%d %d", &a, &b);
        printf("%d\n", g.dist[a][b]);
    }

    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：4 ms
内存：400 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
用时：4 ms
内存：276 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
用时：107 ms
内存：1432 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
用时：105 ms
内存：1408 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
用时：105 ms
内存：1396 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
用时：108 ms
内存：1408 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
用时：108 ms
内存：1412 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
用时：106 ms
内存：1404 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
用时：105 ms
内存：1344 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
用时：101 ms
内存：1348 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.