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 angiing1222 @ 2023-11-03 17:57:31

dijk

by Mikefeng @ 2023-11-03 17:57:47

dij 吧

by Crsuh2er0 @ 2023-11-03 17:59:10

@Mikefeng 那这 Dijkstra 好奇怪，能跑负权图？

在 AcWing 上甚至已经过了 SPFA 板子

by Rainylower @ 2023-11-03 17:59:47

堆优Dij，SPFA的原理是利用队列优化m轮的松弛操作

by 红黑树 @ 2023-11-03 18:01:19

@Crsuh2er0 这个不是负权图啊。

by Ew_Cors @ 2023-11-03 18:01:30

@Crsuh2er0 那应该是数据太水导致的。

by Rainylower @ 2023-11-03 18:01:44

@Crsuh2er0 SPFA板子那道题有判断负环吗？如果没有的话说明都是非负权边，Dij当然可以过

by Crsuh2er0 @ 2023-11-03 18:02:09

@红黑树 在 AcWing 上跑的负权图

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

@Rainylower 没有负环判断，但是题目描述写了有负权边

by Crsuh2er0 @ 2023-11-03 18:05:17

在 AcWing 上的代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 100010
int n,m,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({1,dis[1] = 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(){
    cin.tie(0) -> ios::sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1,u,v,w;i <= m;i++){
        cin>>u>>v>>w;
        p[u].push_back({v,w});
    }
    Dijkstra();
    if(dis[n] == INT_MAX) cout<<"impossible";
    else cout<<dis[n];
    return 0;
}