mxqz 最短路板子

Crsuh2er0 @ 2023-11-03 17:48:59

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 100010
int n,m,s,dis[MAXN];
struct edge{
    int v,w;
    bool operator>(const edge &tmp)const{
        return w > tmp.w;
    }
};
basic_string<edge> p[MAXN];
priority_queue<edge,basic_string<edge>,greater<edge> > q; 
void Dijkstra(){
    fill(dis,dis + n + 1,INT_MAX);
    q.push({s,dis[s] = 0});
    while(!q.empty()){
        int u = q.top().v,d = q.top().w;
        q.pop();
        if(d != dis[u]) continue;
        for(const auto &[v,w] : p[u]){
            if(dis[v] > LL(dis[u]) + w){
                dis[v] = dis[u] + w;
                q.push({v,dis[v]});
            }
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("P4779.in","r",stdin);
    #endif
    cin.tie(0) -> ios::sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m>>s;
    for(int i = 1,u,v,w;i <= m;i++){
        cin>>u>>v>>w;
        p[u].push_back({v,w});
    }
    Dijkstra();
    for(int i = 1;i <= n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

by Crsuh2er0 @ 2023-11-03 18:07:28

@angiing1222 经典 Dijkstra 写法是用一个 vis 数组来判断某个点是否重复入队，我这里改成了 if(d != dis[u]) continue;

by Ew_Cors @ 2023-11-03 18:07:33

@Crsuh2er0 dij 本身不能跑负权图，但是如果数据足够弱是可以通过的。

by 红黑树 @ 2023-11-03 18:09:41

能不能发个 acwing 链接。

by Ew_Cors @ 2023-11-03 18:10:00

@Crsuh2er0 你这个是不是可以卡。

我给你一张 所有边边权全为 -1 并且总是从编号小的点连向编号大的点（连满），这样你的复杂度似乎是 O(n^3\log n) 的？

by angiing1222 @ 2023-11-03 18:10:18

@Crsuh2er0 对不起，刚刚眼瞎了

by Crsuh2er0 @ 2023-11-03 18:15:31

@红黑树 https://www.acwing.com/problem/content/853/

by Crsuh2er0 @ 2023-11-03 18:19:50

@Rainylower 不过它确实跑不了负环

by reveal @ 2023-11-03 20:10:37

@Ew_Cors @Crsuh2er0 不只是 O(n^3\log n) 与负环，实际上，在负权图上使用无限制入队的 Dijsktra 的复杂度是指数级的（或者说伪多项式 O(V)）

例如：

61 90 1
1 3 -1073741824
1 2 -1073741823
2 3 -1073741823
3 5 -536870912
3 4 -536870911
4 5 -536870911
5 7 -268435456
5 6 -268435455
6 7 -268435455
7 9 -134217728
7 8 -134217727
8 9 -134217727
9 11 -67108864
9 10 -67108863
10 11 -67108863
11 13 -33554432
11 12 -33554431
12 13 -33554431
13 15 -16777216
13 14 -16777215
14 15 -16777215
15 17 -8388608
15 16 -8388607
16 17 -8388607
17 19 -4194304
17 18 -4194303
18 19 -4194303
19 21 -2097152
19 20 -2097151
20 21 -2097151
21 23 -1048576
21 22 -1048575
22 23 -1048575
23 25 -524288
23 24 -524287
24 25 -524287
25 27 -262144
25 26 -262143
26 27 -262143
27 29 -131072
27 28 -131071
28 29 -131071
29 31 -65536
29 30 -65535
30 31 -65535
31 33 -32768
31 32 -32767
32 33 -32767
33 35 -16384
33 34 -16383
34 35 -16383
35 37 -8192
35 36 -8191
36 37 -8191
37 39 -4096
37 38 -4095
38 39 -4095
39 41 -2048
39 40 -2047
40 41 -2047
41 43 -1024
41 42 -1023
42 43 -1023
43 45 -512
43 44 -511
44 45 -511
45 47 -256
45 46 -255
46 47 -255
47 49 -128
47 48 -127
48 49 -127
49 51 -64
49 50 -63
50 51 -63
51 53 -32
51 52 -31
52 53 -31
53 55 -16
53 54 -15
54 55 -15
55 57 -8
55 56 -7
56 57 -7
57 59 -4
57 58 -3
58 59 -3
59 61 -2
59 60 -1
60 61 -1

by Ew_Cors @ 2023-11-03 20:25:26

@reveal 这下献丑了，拜谢/bx

by Crsuh2er0 @ 2023-11-04 15:42:14

@reveal orz，拜谢 dalao！