XieGuiYi_aic @ 2022-08-05 09:57:25
#include<bits/stdc++.h>
#define visited vd
using namespace std;
struct Edge
{
int to;
int w;
int next;
}edge[314514];
struct node
{
int w;
int to;
bool operator < (const node &a) const{
return w<a.w;
}
};
int head[314514],dis[314514],cnt;
bool visited[314514];
priority_queue<node> q;
void add(int u,int v,int w)
{
cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
return;
}
int read()
{
char t=getchar();
int k=0;
int fushu=1;
for(;t<'0'||t>'9';t=getchar()) if(t=='-') fushu=-1;
for(;t>='0'&&t<='9';t=getchar()) k=k*10+(t-'0');
return k*fushu;
}
void dijkstra(int start)
{
memset(dis,0x7f,sizeof(dis));
dis[start]=0;
q.push((node){0,start});
while(!q.empty())
{
node t=q.top();
q.pop();
int k=t.to;
if(vd[k]==true)
continue;
vd[k]==true;
for(int i=head[k];i;i=edge[i].next)
{
if(dis[edge[i].to]>dis[k]+edge[i].w)
{
dis[edge[i].to]=dis[k]+edge[i].w;
if(visited[edge[i].to]==false)
q.push((node){dis[edge[i].to],edge[i].to});
}
}
}
return;
}
int n,m,s;
int main()
{
edge[0].next=-1;
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w);
}
dijkstra(s);
for(int i=1;i<=n;i++)
cout<<dis[i]<<' ';
return 0;
}
不知道哪里错了?
by Strelitzia_ @ 2022-08-05 10:08:41
dijkstra
里面第 vd[k]==true
改成 vd[k]=true
。
by cfkk @ 2022-08-05 10:12:12
@lnwhl 上课摸鱼!!!!!
by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:09
priority初始是大根堆
by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:28
bool operator < (const node &a) const{
return w>a.w;
}
这样就可以了
by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:34
@Strelitzia_
by Strelitzia_ @ 2022-08-05 10:20:04
@qwq_volcano 您是不是 @
错人了
by XieGuiYi_aic @ 2022-08-05 10:21:41
谢谢,已A
by PRIMITIVE_LIGHTS @ 2022-08-05 10:27:36
@Strelitzia_ 好吧