提交记录 #5926 - BNBU Online Judge System

编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#5926	#1061. 最短路问题	Wrong Answer	0	3778 ms	68148 K	C++ 17 / 4.2 K	s230026152	2024-08-17 17:38:30

显示原始代码

/**
 * @title: ..
 * @desc: ..
 * @tag: IO
 * @url:
 */

#include <bits/stdc++.h>

/*
 *
 *   宏定义模板常量:
 *
 *          使用STD
 *          重复数据读入
 *          int强制转ll
 *          重载工具函数
 *          启用debug输出
 *          关闭输入同步流
 *          使用文件输入流
 *          使用文件输出流
 *
 */

#define USE_STD

#define USE_LL

// #define REAP_READ
#define USE_TOOL

// #define USE_DEBUG
// #define USE_IOS
// #define IN_FILE "data.in"
// #define OUT_FILE "solve.out"

#ifdef USE_STD
using namespace std;
#endif

#ifdef USE_LL
#define int long long

#endif

// 辅助宏
#define rep(i, l, r) for (int i = (l); i < (r); i++)

#define _rep(i, l, r) for (int i = (l); i >= (r); i--)

#define all(x) (x).begin(), x.end()

#define endl '\n'  // 避免刷新缓冲区

#define inf32 0x3f3f3f3f

#define max32 INT_MAX

#define inf64 1LL << 60


// 类型别名
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using pii = std::pair<int, int>;

// 常规输出
template <typename T>
void print(const T &t) {
    std::cout << t << endl;
}
template <typename T, typename... Args>
void print(const T &t, const Args... args) {
    std::cout << t << ' ';
    print(args...);
}

// USE_DEBUG 模式下的输出
template <typename T>
void debug(const T &t) {
#ifdef USE_DEBUG
    std::cout << t << "\n\n";
#endif
}
template <typename T, typename... Args>
void debug(const T &t, const Args... args) {
#ifdef USE_DEBUG
    std::cout << t << ' ';
    debug(args...);
#endif
}

#ifdef USE_TOOL
i64 ceilDiv(i64 n, i64 m) {
    if (n >= 0) {
        return (n + m - 1) / m;
    } else {
        return n / m;
    }
}

i64 floorDiv(i64 n, i64 m) {
    if (n >= 0) {
        return n / m;
    } else {
        return (n - m + 1) / m;
    }
}

template <class T>
void chmax(T &a, T b) {
    if (a < b) {
        a = b;
    }
}

template <class T>
void chmin(T &a, T b) {
    if (a > b) {
        a = b;
    }
}

i128 gcd(i128 a, i128 b) { return b ? gcd(b, a % b) : a; }
#endif

// 快读快写
int read();
void write(int);

const int N = 5e5 + 5;
const int MOD = 1e9 + 7;

void solve() {
    int n = read(), m = read();
    vector<vector<pii>> g(n);
    rep(i, 0, m) {
        int x = read() - 1, y = read() - 1, z = read();
        g[x].push_back({ y, z });
        g[y].push_back({ x, z });
    }
    rep(i, 0, n - 1) {
        g[i].push_back({ i + 1, 1 });
        g[i + 1].push_back({ i, 1 });
    }
    vector<int> dist(n, inf64);
    dist[0] = 0;
    vector<int> vis(n);
    priority_queue<pii> hp;
    hp.push({ 0, 0 });
    while (hp.size()) {
        int d = hp.top().first, u = hp.top().second;
        hp.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto son : g[u]) {
            int v = son.first;
            int w = son.second;
            int cost = dist[u] + w;
            if (cost < dist[v]) {
                dist[v] = cost;
                hp.push({ dist[v], v });
            }
        }
    }
    string f;
    rep(i, 1, n) {
        if (i != n - 1)
            f = " ";
        else
            f = endl;
        cout << dist[i] << f;
    }
}

signed main() {
    int T = 1;
    debug("hello world");
#ifdef IN_FILE
    freopen(IN_FILE, "r", stdin);
#endif

#ifdef OUT_FILE
    freopen(OUT_FILE, "w", stdout);
#endif

#ifdef REAP_READ
    std::cin >> T;
#endif

#ifdef USE_IOS
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    while (T--) {
        solve();
    }
    return 0;
}

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

子任务 #1

Wrong Answer

得分：0

测试点 #1

Wrong Answer

得分：0

用时：4 ms

内存：404 KiB

输入文件（paths1.in）

答案文件（paths1.out）

1 2 3 3 2 3 4 4 5

用户输出

1 2 4 3 2 3 4 4 5

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #2

Wrong Answer

得分：0

用时：2 ms

内存：384 KiB

输入文件（paths2.in）

答案文件（paths2.out）

1 2 3 4 5 5 4 5 5

用户输出

1 2 14 11 10 9 4 11 12

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #3

Wrong Answer

得分：0

用时：4 ms

内存：384 KiB

输入文件（paths3.in）

答案文件（paths3.out）

1 2 3 2 3 4 3 4 5

用户输出

1 2 10 2 6 5 3 7 8

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #4

Wrong Answer

得分：0

用时：3 ms

内存：268 KiB

输入文件（paths4.in）

答案文件（paths4.out）

1 2 3 4 5 5 6 5 6

用户输出

1 2 10 9 10 10 9 8 9

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #5

Wrong Answer

得分：0

用时：3 ms

内存：380 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 47064 14713 14712 7988 14065 14713 9192 24914 41089 36632 14214 278 277 278 10542 35965 29673 29672 29673 3630 35731 13325 1
<5472 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #6

Wrong Answer

得分：0

用时：4 ms

内存：500 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 6391 23325 16241 16240 16241 35609 35610 51436 51435 190 189 188 189 190 191 192 38764 38066 20914 8305 19453 32275 23060 
<5433 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #7

Wrong Answer

得分：0

用时：3 ms

内存：484 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 4150 12302 59091 49887 42456 4596 36863 36862 36863 19304 4404 32954 49149 10331 17617 3792 23919 35044 51983 43550 64175 
<5505 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #8

Wrong Answer

得分：0

用时：3 ms

内存：512 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 37155 2996 37173 51531 15072 51529 23748 42768 43778 43777 32006 21328 32006 28437 10416 14328 37157 4279 7605 7604 7605 760
<5486 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #9

Wrong Answer

得分：0

用时：27 ms

内存：7784 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
<588760 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #10

Wrong Answer

得分：0

用时：29 ms

内存：7728 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
<589098 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #11

Wrong Answer

得分：0

用时：29 ms

内存：7764 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
<588760 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #12

Wrong Answer

得分：0

用时：27 ms

内存：7776 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
<588760 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #13

Wrong Answer

得分：0

用时：30 ms

内存：7868 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
<681451 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #14

Wrong Answer

得分：0

用时：30 ms

内存：7788 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
<695515 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #15

Wrong Answer

得分：0

用时：30 ms

内存：7724 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
<681599 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #16

Wrong Answer

得分：0

用时：30 ms

内存：7900 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
<678638 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #17

Wrong Answer

得分：0

用时：971 ms

内存：68084 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 1112495951 1112495950 1112495951 1112495952 1112495953 2289229275 13801914736 2022842690 13801914734 2449978272 2449978271 2
<5482784 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #18

Wrong Answer

得分：0

用时：873 ms

内存：68136 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 1149656721 1149656722 1549493736 5527349621 5527349620 2253215868 5527349622 1250410462 485082321 1250410462 5037190738 6563
<5484565 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #19

Wrong Answer

得分：0

用时：900 ms

内存：68120 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 770044646 1506823074 10736767672 6785295361 6875499836 10736767671 2095828980 8309304450 4585476917 837976359 10726362132 12
<5482951 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #20

Wrong Answer

得分：0

用时：776 ms

内存：68148 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 634342505 2777720534 2777720533 2777720534 1263918509 1096741974 1263918507 1263918508 1263918509 8659544710 15045851685 150
<5481434 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0