首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#5684 #1061. 最短路问题 Accepted 100 5239 ms 110700 K C++ 17 / 1.7 K TosakaUCW 2024-08-17 14:14:50
显示原始代码 
#include <bits/stdc++.h>
using i64 = long long;
#define int long long

#define pb push_back

using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while (48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const i64 INF = 1LL << 60;

struct node {
    int cur;
    i64 dis;
    bool friend operator<(node a, node b) { return a.dis > b.dis; }
};

void solve() {
    int n = read(), m = read();

    vector<bool> vis(2 * n + 5);
    vector<i64> dis(2 * n + 5, INF);
    std::priority_queue<node> Q;
    vector<vector<std::pair<int, i64>>> g(2 * n + 5);

    auto add = [&](int u, int v, i64 dis) { g[u].pb({ v, dis }); };

    for (int i = 1, u, v, d; i <= m; i++) u = read(), v = read(), d = read(), add(u, v, d), add(v, u, d);

    for (int i = 1; i <= n; i++) add(i, i + n + 1, 0), add(i + n + 1, i, 0);

    for (int i = 1; i < n; i++) {
        int u = i + n + 1;
        int v = i + n + 2;
        add(u, v, 1);
        add(v, u, 1);
    }

    dis[1] = 0, Q.push({ 1, 0 });
    for (int u; !Q.empty();) {
        u = Q.top().cur, Q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto [v, dist] : g[u])
            if (dis[v] > dis[u] + dist)
                dis[v] = dis[u] + dist, Q.push({ v, dis[v] });
    }
    for (int i = 2; i <= n; i++) cout << dis[i] << ' ';
    puts("");
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("paths1.in", "r", stdin);
    freopen("paths1.ans", "w", stdout);
#endif
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：3 ms
内存：236 KiB

输入文件（paths1.in） 

10 10
10 6 4
5 3 1
9 6 2
4 5 1
4 9 3
3 2 1
6 1 2
9 7 2
6 1 5
3 7 3

答案文件（paths1.out） 

1 2 3 3 2 3 4 4 5

用户输出 

1 2 3 3 2 3 4 4 5

系统信息 

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

输入文件（paths2.in） 

10 10
10 3 10
7 9 3
3 8 5
1 7 9
2 8 3
7 9 2
8 5 2
2 5 10
10 4 2
3 6 9

答案文件（paths2.out） 

1 2 3 4 5 5 4 5 5

用户输出 

1 2 3 4 5 5 4 5 5

系统信息 

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

输入文件（paths3.in） 

10 10
8 2 2
3 5 1
5 2 1
7 1 5
7 5 4
5 2 2
3 2 1
8 6 2
7 8 2
4 5 1

答案文件（paths3.out） 

1 2 3 2 3 4 3 4 5

用户输出 

1 2 3 2 3 4 3 4 5

系统信息 

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

输入文件（paths4.in） 

10 10
7 10 3
10 5 4
5 9 1
3 4 1
3 10 7
9 10 8
4 3 1
4 10 10
9 1 8
7 4 2

答案文件（paths4.out） 

1 2 3 4 5 5 6 5 6

用户输出 

1 2 3 4 5 5 6 5 6

系统信息 

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

输入文件（paths5.in） 

1000 1000
386 311 62
947 590 264
442 765 286
781 232 263
342 830 357
254 490 144
787 531 157
856 254
<11270 bytes omitted>

答案文件（paths5.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 20 19 18 17 16 15 14 13 12 11 10 9 10 11 12
<2888 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 20 19 18 17 16 15 14 13 12 11 10 9 10 11 12 13 14 15 16 17 18 19 20 21 
<2860 bytes omitted>

系统信息 

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

输入文件（paths6.in） 

1000 1000
488 851 248
98 734 233
785 205 551
545 950 234
999 300 205
341 592 88
440 152 108
157 840 
<11248 bytes omitted>

答案文件（paths6.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 30 29 30 29 28 2
<2876 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 30 29 30 29 28 27 26 25 24 23 22 21 20 19 18
<2848 bytes omitted>

系统信息 

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

输入文件（paths7.in） 

1000 1000
183 188 4
320 628 957
199 480 161
31 78 47
328 607 99
458 436 743
367 158 180
309 802 365

<11245 bytes omitted>

答案文件（paths7.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2886 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 37 36 35 34 33 32 31 30
<2858 bytes omitted>

系统信息 

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

输入文件（paths8.in） 

1000 1000
606 400 26
81 139 5
108 603 19
522 245 23
846 344 110
53 832 279
848 274 196
174 2 72
445 
<11235 bytes omitted>

答案文件（paths8.out） 

1 2 3 4 5 6 7 8 9 10 11 12 11 10 9 8 7 6 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2
<2880 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 11 10 9 8 7 6 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 25 24 23 24 25 26 27 28 29
<2852 bytes omitted>

系统信息 

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

输入文件（paths9.in） 

100000 1
42869 67934 9980

答案文件（paths9.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<588789 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<588761 bytes omitted>

系统信息 

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

输入文件（paths10.in） 

100000 1
76540 44829 23801

答案文件（paths10.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<588789 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<588761 bytes omitted>

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：49 ms
内存：18352 KiB

输入文件（paths11.in） 

100000 1
10834 66572 6137

答案文件（paths11.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<588789 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<588761 bytes omitted>

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：69 ms
内存：18416 KiB

输入文件（paths12.in） 

100000 1
23418 78501 17434

答案文件（paths12.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<588789 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<588761 bytes omitted>

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：58 ms
内存：18352 KiB

输入文件（paths13.in） 

100000 30
66577 27574 15989
57497 64234 3847
70344 91131 2067
12766 80177 35761
73332 38638 20188
75
<419 bytes omitted>

答案文件（paths13.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<587443 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<587415 bytes omitted>

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：56 ms
内存：18440 KiB

输入文件（paths14.in） 

100000 30
476 59661 55988
76799 59777 6131
32697 88275 42059
34218 89384 5643
38185 67617 13787
6859
<432 bytes omitted>

答案文件（paths14.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<588789 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<588761 bytes omitted>

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：51 ms
内存：18400 KiB

输入文件（paths15.in） 

100000 30
2128 30547 18765
40047 80322 33301
82136 70025 7516
33768 66814 17118
37952 52558 12476
17
<431 bytes omitted>

答案文件（paths15.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<585958 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<585930 bytes omitted>

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：52 ms
内存：18356 KiB

输入文件（paths16.in） 

100000 30
77808 31672 35610
95082 46111 19236
44217 14265 1945
92386 1818 65252
65053 23506 9679
555
<422 bytes omitted>

答案文件（paths16.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<585248 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<585220 bytes omitted>

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：1145 ms
内存：110540 KiB

输入文件（paths17.in） 

500000 500000
119637 206482 5305
415079 298250 7615
287208 350360 25447
82077 159253 21971
14650 475
<9909079 bytes omitted>

答案文件（paths17.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2479290 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<2479262 bytes omitted>

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：1252 ms
内存：110604 KiB

输入文件（paths18.in） 

500000 500000
32801 418343 23967
144010 479613 186699
411707 108288 49326
433635 393879 37266
371524
<9908808 bytes omitted>

答案文件（paths18.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2450396 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<2450368 bytes omitted>

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：1123 ms
内存：110600 KiB

输入文件（paths19.in） 

500000 500000
314249 208397 97409
189367 482804 231718
65738 427855 14488
131958 119538 455022
17299
<9907866 bytes omitted>

答案文件（paths19.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2433098 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<2433070 bytes omitted>

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：1264 ms
内存：110700 KiB

输入文件（paths20.in） 

500000 500000
382560 319678 36825
410794 160089 354323
446438 486682 35533
227226 90930 13771
172509
<9907538 bytes omitted>

答案文件（paths20.out） 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3
<2307648 bytes omitted>

用户输出 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
<2307620 bytes omitted>

系统信息 

Exited with return code 0
BNBU Online Judge System Powered by SYZOJ.