Greenzhe @ 2022-09-03 09:10:54
建的是有向边,数组也没有开小,求问各位大佬哪里写挂了
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
int dis[100005];
bool vis[100005];
struct edge{
int v,w; //v终点,w权值
};
vector<edge> rel[100005];
const int INF=0x3f3f3f3f;
void dijkstra();
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
rel[u].push_back({v,w});
}
memset(dis,0x3f,sizeof(dis));
dijkstra();
for(int i=1;i<=n;++i)
printf("%d ",dis[i]);
printf("\n");
return 0;
}
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
}; //自定义比较仿函数,用于小根堆
void dijkstra(){
priority_queue<int,vector<int>,cmp> q;
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int x=q.top();
q.pop();
for(int i=0;i<rel[x].size();++i){
int y=rel[x][i].v;
if(dis[x]+rel[x][i].w<dis[y]){
dis[y]=dis[x]+rel[x][i].w;
if(!vis[y]){
vis[y]=true;
q.push(y);
}
}
}
}
}
by yinhee @ 2022-09-03 09:35:22
@蒟蒻·廖子阳 这就是spfa吧……
by lzyqwq @ 2022-09-03 09:36:08
@yinhee 但是他用了优先队列
by lzyqwq @ 2022-09-03 09:36:35
@yinhee 不就比spfa更假了吗(
by Seal_l @ 2022-09-03 09:38:19
sptra!
by Greenzhe @ 2022-09-03 09:38:37
玄学(雾
by FiraCode @ 2022-09-03 09:38:51
@Seal_l woc!
by yinhee @ 2022-09-03 09:39:20
@蒟蒻·廖子阳 dijkspfa(雾
by Greenzhe @ 2022-09-03 09:40:49
我去loj上测测
by Greenzhe @ 2022-09-03 09:42:40
loj上也过了(
by Greenzhe @ 2022-09-03 09:44:54
那么好吧,此贴先结了
@蒟蒻·廖子阳 @李佳和 @FiraCode @yinhee @Seal_l
谢谢大佬