hayoon @ 2023-11-12 09:29:23
#include<bits/stdc++.h>
using namespace std;
int head[200000];
long long dis[200000];
bool visit[200000];
int cnt=0;
struct edge
{
int z;
int val;
int nexty;
}edge[1000000];
inline void add(int a,int b,int c)
{
cnt++;
edge[cnt].z=b;
edge[cnt].val=c;
edge[cnt].nexty=head[a];
head[a]=cnt;
}
int main()
{
int n,m,s;
int a,b,c;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)
dis[i]=INT_MAX;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int curr=s;
dis[s]=0;
long long minn;
while(!visit[curr])
{
visit[curr]=1;
int i=head[curr];
while(i!=0)
{
if(!visit[edge[i].z] && dis[edge[i].z]>dis[curr]+edge[i].val)
dis[edge[i].z]=dis[curr]+edge[i].val;
i=edge[i].nexty;
}
minn=INT_MAX;
for(int i=1;i<=n;i++)
{
if(!visit[i]&&minn>dis[i])
{
minn=dis[i];
curr=i;
}
}
}
for(int i=1;i<=n;i++)
printf("%lld ",dis[i]);
return 0;
}
真·不·理解
by wizard(偷开O2 @ 2023-11-12 09:59:02
1.建议改一下
2.你的代码弱化版能过,标准版数据很强,加
by wizard(偷开O2 @ 2023-11-12 09:59:20
@hayoon