dijk
by angiing1222 @ 2023-11-03 17:57:31
dij 吧
by Mikefeng @ 2023-11-03 17:57:47
@[Mikefeng](/user/406832) 那这 Dijkstra 好奇怪，能跑负权图？
在 AcWing 上甚至已经过了 SPFA 板子
by Crsuh2er0 @ 2023-11-03 17:59:10
堆优Dij，SPFA的原理是利用队列优化m轮的松弛操作
by Rainylower @ 2023-11-03 17:59:47
@[Crsuh2er0](/user/762775) 这个不是负权图啊。
by 红黑树 @ 2023-11-03 18:01:19
@[Crsuh2er0](/user/762775) 那应该是数据太水导致的。
by Ew_Cors @ 2023-11-03 18:01:30
@[Crsuh2er0](/user/762775) SPFA板子那道题有判断负环吗？如果没有的话说明都是非负权边，Dij当然可以过
by Rainylower @ 2023-11-03 18:01:44
@[红黑树](/user/413140) 在 AcWing 上跑的负权图
by Crsuh2er0 @ 2023-11-03 18:02:09
@[Rainylower](/user/275079) 没有负环判断，但是题目描述写了有负权边
by Crsuh2er0 @ 2023-11-03 18:04:31
在 AcWing 上的代码如下：
```cpp
#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;
}
```
by Crsuh2er0 @ 2023-11-03 18:05:17