jdv23442 @ 2022-03-30 21:34:03
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn = 100005,INF = 99999999;
int n,m,s;
struct node{
int to,w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];
void dijkstra() {
dis[s] = 0;
queue<int> q;
q.push(s);
vis[s] = true;
while(!q.empty()) {
int p = q.front(); q.pop();
cout<<"pop "<<p<<endl;
int size = e[p].size();
int minP = INF, minPos = 0; // 最小值,最小值对应的点
for(int i=0;i<size;i++) {
int t = e[p][i].to;
int w = e[p][i].w;
dis[t] = min(dis[t],dis[p]+w);
if(dis[t] < minP && !vis[t]) {
minP = dis[t];
minPos = t;
}
}
if(minP != INF) {
vis[minPos] = true;
q.push(minPos);
}
}
}
int main(){
cin>>n>>m>>s;
int u,v,w;
for(int i=1;i<=m;i++) {
cin>>u>>v>>w;
node p; p.to = v; p.w = w;
e[u].push_back(p);
}
for(int i=1;i<=n;i++)
dis[i] = INF;
dijkstra();
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
by LYqwq @ 2022-03-30 21:36:19
queue<int> q;
大无语
建议重学
by jdv23442 @ 2022-03-30 21:47:03
@LYqwq 这有什么不行吗?
by LYqwq @ 2022-03-30 21:48:56
如果你懂 dij 的原理的话咋可能这么写,样例能过都是奇迹
by jdv23442 @ 2022-03-30 21:55:38
@LYqwq 感谢你的回复!我这也是第一次写dij,本来不会写,看题解的思路写的。感觉没什么问题啊!初始化源点距离为0,其他INF,每次选一个距离最小的点入队,遍历并更新它的出点的距离,再把最小的一个点加入队列,并标记访问,这没什么不对啊!
by jdv23442 @ 2022-03-30 21:57:50
看其他讨论后增加了边的去重,还是不行
cin>>n>>m>>s;
int u,v,w;
for(int i=1;i<=m;i++) {
cin>>u>>v>>w;
int flag = true;
for(int i=0;i<e[u].size();i++) {
if(e[u][i].to == v) {
flag = false;
e[u][i].w = max(e[u][i].w,w);
}
}
if(flag) e[u].push_back((node){v,w});
}
by Sharpsmile @ 2022-03-30 21:58:33
@jdv23442 啊这这这,dij是在所有点之中选择最近的,不是只有这次更新过的啊。。。。。。
by junxis @ 2022-03-30 21:58:40
@jdv23442
DIJ怎么可能是用queue实现的啊?
要么set要么priority_queue啊。。。
by Sharpsmile @ 2022-03-30 21:59:09
所有指所有没有遍历过的节点
by jdv23442 @ 2022-03-30 22:00:50
确实是,确实是,原理还没搞懂就写了。。。 感谢大家!