编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#5767 #1063. 分身游走 Wrong Answer 0 8414 ms 1176 K C++ 17 / 1.6 K s230004040 2024-08-17 15:12:10
显示原始代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

struct Edge {
    int to, weight;
};

// Function to perform Dijkstra's algorithm
vector<int> dijkstra(int start, int n, const vector<vector<Edge>>& graph) {
    vector<int> distances(n + 1, INT_MAX);
    distances[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (dist > distances[u])
            continue;

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
                pq.push({ distances[v], v });
            }
        }
    }

    return distances;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<vector<Edge>> graph(n + 1);

    // Reading the graph edges
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({ v, w });
        graph[v].push_back({ u, w });
    }

    // Calculate for each city
    for (int start = 1; start <= n; ++start) {
        vector<int> distances = dijkstra(start, n, graph);
        sort(distances.begin() + 1, distances.end());

        int totalDistance = 0;
        for (int i = 1; i <= k; ++i) {
            totalDistance += distances[i];
        }

        cout << totalDistance << endl;
    }

    return 0;
}
子任务 #1
Wrong Answer
得分:0
测试点 #1
Wrong Answer
得分:0
用时:3 ms
内存:244 KiB

输入文件(move1.in

10 1
1 2 97
1 3 17
2 4 79
2 5 19
1 6 54
4 7 28
5 8 39
7 9 63
8 10 35

答案文件(move1.out

595
692
578
632
673
541
604
634
541
599

用户输出

0
0
0
0
0
0
0
0
0
0

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #2
Wrong Answer
得分:0
用时:3 ms
内存:276 KiB

输入文件(move2.in

10 1
1 2 100
2 3 98
1 4 4
2 5 29
3 6 33
3 7 33
7 8 53
1 9 86
4 10 15

答案文件(move2.out

618
716
618
614
687
585
585
532
532
599

用户输出

0
0
0
0
0
0
0
0
0
0

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #3
Wrong Answer
得分:0
用时:3 ms
内存:268 KiB

输入文件(move3.in

20 2
1 2 61
2 3 95
1 4 68
4 5 15
4 6 54
4 7 45
2 8 81
8 9 77
4 10 26
2 11 40
9 12 16
11 13 45
11 14 
<53 bytes omitted>

答案文件(move3.out

1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303
1303

用户输出

61
40
95
15
15
54
45
77
16
26
24
16
45
15
6
7
26
46
83
6

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #4
Wrong Answer
得分:0
用时:2 ms
内存:384 KiB

输入文件(move4.in

20 2
1 2 76
1 3 81
3 4 40
2 5 16
5 6 12
3 7 87
5 8 3
3 9 42
6 10 33
5 11 13
2 12 43
2 13 13
13 14 64
<49 bytes omitted>

答案文件(move4.out

1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318
1318

用户输出

76
13
40
38
3
12
87
3
42
33
13
43
13
64
53
8
90
38
8
76

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #5
Wrong Answer
得分:0
用时:2 ms
内存:284 KiB

输入文件(move5.in

50 12
1 2 48
1 3 18
2 4 63
4 5 69
5 6 77
5 7 96
7 8 2
1 9 19
5 10 94
9 11 45
1 12 33
7 13 11
8 14 24
<309 bytes omitted>

答案文件(move5.out

3657
3581
3789
3789
3651
3807
3807
3811
3757
4006
4001
3840
3888
3965
3968
3968
4089
3779
3822
4054

<150 bytes omitted>

用户输出

616
658
796
1087
1036
1348
369
365
714
1788
1074
820
479
605
1756
970
992
1363
911
2028
497
1303
2153
1542
1274
1161
1030
1723
1
<104 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #6
Wrong Answer
得分:0
用时:3 ms
内存:244 KiB

输入文件(move6.in

50 11
1 2 46
2 3 54
2 4 24
1 5 77
2 6 5
4 7 89
7 8 57
2 9 45
2 10 6
5 11 39
6 12 66
12 13 78
1 14 89
<308 bytes omitted>

答案文件(move6.out

3103
2943
3391
3063
3586
2975
3468
3523
3318
2997
3713
3321
3743
3664
3567
3637
3765
3015
3673
3723

<150 bytes omitted>

用户输出

670
351
789
492
965
396
841
532
620
393
1084
760
1306
1194
622
1211
1487
411
1061
1307
1248
1453
1613
977
542
688
1032
1010
1651
<99 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #7
Wrong Answer
得分:0
用时:3 ms
内存:356 KiB

输入文件(move7.in

50 12
1 2 20
2 3 75
3 4 51
3 5 51
1 6 88
5 7 34
6 8 96
5 9 16
8 10 56
2 11 64
3 12 8
2 13 82
4 14 93
<311 bytes omitted>

答案文件(move7.out

3955
3904
4167
4481
4350
4398
4486
4609
4446
4757
4368
4231
4252
4795
4505
4338
4504
4669
4873
4804

<150 bytes omitted>

用户输出

915
872
626
981
767
1441
903
1416
903
1864
1512
690
1188
1766
1021
1392
1564
1869
2656
1573
1900
2157
943
1633
1302
1546
1722
21
<111 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #8
Wrong Answer
得分:0
用时:7 ms
内存:244 KiB

输入文件(move8.in

200 20
1 2 95
2 3 24
1 4 15
1 5 58
1 6 86
4 7 5
1 8 4
7 9 22
1 10 78
5 11 64
4 12 67
11 13 11
5 14 6
<1777 bytes omitted>

答案文件(move8.out

15928
16836
17098
16108
16395
17390
16198
15976
16594
16922
17191
17123
17284
17057
17317
17458
1768
<1100 bytes omitted>

用户输出

976
1469
1576
1022
1457
2267
1082
992
1478
1713
1860
1694
1860
1094
2184
1415
1999
1757
1928
1511
2036
2212
1891
2114
2802
2986

<870 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #9
Wrong Answer
得分:0
用时:8 ms
内存:316 KiB

输入文件(move9.in

200 20
1 2 58
2 3 100
1 4 42
4 5 5
5 6 47
6 7 61
5 8 9
7 9 2
5 10 71
1 11 96
10 12 58
12 13 16
11 14
<1786 bytes omitted>

答案文件(move9.out

16921
17763
18734
16461
16391
17174
17885
16481
17915
16532
17793
17404
17633
18708
17858
16715
1729
<1100 bytes omitted>

用户输出

1500
2103
2763
979
899
1454
1417
908
1437
1373
1612
1595
1746
2800
2688
1437
2057
2304
998
1148
1365
2481
3345
2339
1476
1476
20
<868 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #10
Wrong Answer
得分:0
用时:7 ms
内存:300 KiB

输入文件(move10.in

200 20
1 2 32
2 3 29
1 4 4
2 5 18
4 6 76
2 7 77
7 8 43
6 9 56
5 10 61
4 11 61
8 12 45
9 13 50
12 14 
<1756 bytes omitted>

答案文件(move10.out

15907
15837
16178
15907
15954
16604
16666
17203
16757
16497
16624
17571
17207
17757
16981
16234
1672
<1100 bytes omitted>

用户输出

954
947
1170
952
1126
1847
1704
1896
1573
1475
1008
1830
1760
1830
1219
1181
1532
2882
2981
1672
1847
1862
3067
1525
1760
2966
2
<868 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #11
Wrong Answer
得分:0
用时:7 ms
内存:296 KiB

输入文件(move11.in

200 20
1 2 42
1 3 74
1 4 35
1 5 44
1 6 99
1 7 48
1 8 10
1 9 68
1 10 20
1 11 53
1 12 88
1 13 15
1 14 
<1575 bytes omitted>

答案文件(move11.out

17254
18010
18586
17884
18046
18934
18118
17434
18478
17614
18208
18838
17524
17470
18082
18922
1808
<1100 bytes omitted>

用户输出

90
878
1486
745
916
1961
992
270
1372
460
1087
1752
365
308
954
1885
954
1163
992
1372
1410
403
144
308
365
1486
1581
840
1011
9
<768 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #12
Wrong Answer
得分:0
用时:7 ms
内存:384 KiB

输入文件(move12.in

200 20
1 2 87
1 3 34
1 4 60
1 5 26
1 6 57
1 7 42
1 8 93
1 9 55
1 10 59
1 11 65
1 12 70
1 13 3
1 14 6
<1574 bytes omitted>

答案文件(move12.out

18638
20204
19250
19718
19106
19664
19394
20299
19628
19700
19808
19898
18692
18746
19448
19970
2031
<1100 bytes omitted>

用户输出

80
1724
717
1211
565
1154
869
1838
1116
1192
1306
1401
134
188
926
1477
1876
1382
983
793
622
603
584
1325
375
1724
1116
489
166
<775 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #13
Time Limit Exceeded
得分:0
用时:1044 ms
内存:996 KiB

输入文件(move13.in

15000 1
1 2 14
2 3 37
3 4 82
4 5 16
5 6 31
4 7 8
3 8 2
3 9 58
5 10 49
7 11 77
11 12 33
7 13 46
6 14 
<194180 bytes omitted>

答案文件(move13.out

1520629
1520643
1520680
1520664
1520648
1520617
1520656
1520678
1520622
1520599
1520579
1520546
1520
<119900 bytes omitted>

用户输出

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

<638 bytes omitted>
测试点 #14
Time Limit Exceeded
得分:0
用时:1005 ms
内存:1052 KiB

输入文件(move14.in

15000 2
1 2 21
1 3 70
3 4 23
3 5 91
3 6 89
3 7 62
6 8 51
3 9 49
4 10 61
2 11 7
2 12 7
12 13 4
12 14 
<194246 bytes omitted>

答案文件(move14.out

1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504140
1504
<119900 bytes omitted>

用户输出

4
7
23
1
15
18
34
11
4
6
7
3
4
10
7
2
37
4
3
12
7
8
26
5
5
8
24
5
14
10
1
2
2
12
11
25
2
9
4
25
17
16
2
38
1
1
32
5
4
15
50
8
2

<825 bytes omitted>
测试点 #15
Time Limit Exceeded
得分:0
用时:1053 ms
内存:1176 KiB

输入文件(move15.in

15000 20
1 2 36
1 3 38
1 4 16
1 5 26
1 6 28
1 7 49
1 8 60
1 9 58
1 10 3
1 11 54
1 12 73
1 13 52
1 14
<152640 bytes omitted>

答案文件(move15.out

1523120
1523768
1523804
1523408
1523588
1523624
1524002
1524200
1524164
1523174
1524092
1524434
1524
<119900 bytes omitted>

用户输出

19
702
740
322
512
550
949
1158
1120
75
1044
1405
1006
911
797
1823
341
56
968
1709
1405
1405
797
455
189
588
1139
1386
968
436

<1608 bytes omitted>
测试点 #16
Time Limit Exceeded
得分:0
用时:1050 ms
内存:1172 KiB

输入文件(move16.in

15000 20
1 2 77
1 3 79
1 4 12
1 5 69
1 6 49
1 7 59
1 8 76
1 9 82
1 10 14
1 11 15
1 12 70
1 13 44
1 1
<152590 bytes omitted>

答案文件(move16.out

1510170
1511556
1511592
1510386
1511412
1511052
1511232
1511538
1511646
1510422
1510440
1511430
1510
<119900 bytes omitted>

用户输出

19
1481
1519
246
1329
949
1139
1462
1576
284
303
1348
854
1329
1158
1158
740
759
227
1386
683
1614
1443
778
1215
759
645
1861
85
<1609 bytes omitted>
测试点 #17
Time Limit Exceeded
得分:0
用时:1052 ms
内存:996 KiB

输入文件(move17.in

15000 20
1 2 100
2 3 94
3 4 12
2 5 92
5 6 62
3 7 87
7 8 35
7 9 96
1 10 71
8 11 88
10 12 46
8 13 53
1
<194039 bytes omitted>

答案文件(move17.out

1497129
1496432
1495734
1495810
1497039
1497768
1495642
1495686
1497134
1497000
1497014
1497320
1496
<119900 bytes omitted>

用户输出

1158
974
642
622
896
755
808
360
675
601
1235
904
903
856
1030
656
1090
357
977
415
1348
664
711
913
870
1407
967
1500
1015
807

<1716 bytes omitted>
测试点 #18
Time Limit Exceeded
得分:0
用时:1052 ms
内存:1036 KiB

输入文件(move18.in

15000 20
1 2 35
1 3 87
2 4 87
1 5 18
2 6 84
1 7 84
4 8 81
2 9 81
3 10 86
7 11 79
10 12 78
3 13 97
3 
<194043 bytes omitted>

答案文件(move18.out

1486904
1487130
1487612
1487627
1487228
1488568
1486986
1488529
1488540
1488227
1487899
1489616
1489
<119900 bytes omitted>

用户输出

818
645
652
718
912
1150
1032
642
844
1586
886
1643
1546
754
1206
811
1174
822
1225
712
1529
1062
523
1509
1478
1091
1587
1099
8
<1710 bytes omitted>
测试点 #19
Time Limit Exceeded
得分:0
用时:1050 ms
内存:1012 KiB

输入文件(move19.in

15000 20
1 2 70
1 3 93
3 4 68
1 5 42
2 6 32
6 7 23
7 8 70
7 9 18
5 10 32
10 11 85
11 12 5
11 13 83
1
<194121 bytes omitted>

答案文件(move19.out

1501326
1501603
1502574
1503070
1501469
1501764
1502040
1503150
1502363
1501569
1501468
1501502
1502
<119900 bytes omitted>

用户输出

1212
1089
964
852
716
781
808
1586
706
1054
684
723
1551
615
859
1198
982
573
831
1380
555
519
567
1394
727
1303
927
1734
1192
1
<1702 bytes omitted>
测试点 #20
Time Limit Exceeded
得分:0
用时:1053 ms
内存:1028 KiB

输入文件(move20.in

15000 20
1 2 92
1 3 25
3 4 11
4 5 69
3 6 25
2 7 54
4 8 79
8 9 7
6 10 16
2 11 95
8 12 11
5 13 8
4 14 
<194235 bytes omitted>

答案文件(move20.out

1509691
1510556
1509480
1509502
1510135
1509792
1511528
1510340
1510466
1510080
1512124
1510494
1510
<119900 bytes omitted>

用户输出

891
823
653
740
705
545
650
873
965
450
1049
842
769
972
1310
1267
800
1172
977
1249
808
2273
1155
1575
2581
853
1162
1192
1568

<1706 bytes omitted>