Jason12 @ 2022-03-01 20:19:44
样例无输出,return value 3221225477
#include <bits/stdc++.h>
using namespace std;
int n,m,l,t,a[100005],c[100005],u,v,w,i,j;
bool d[100005];
struct xy{
int x,y,z;
}b[200005];
void add(int u,int v,int w)
{
b[++l].x=a[u];
a[u]=l;
b[l].y=v;
b[l].z=w;
return;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
memset(a,0x3f,sizeof(a));
a[t]=0;
d[t]=1;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
if (u==t) c[v]=w;
}
for (i=1;i<=n;i++)
{
u=0x3f3f3f3f;
for (j=1;j<=n;j++)
{
if (!d[j] && u>c[j])
{
u=c[j];
v=j;
}
}
d[v]=1;
for (j=a[v];j;j=b[j].x)
{
c[j]=min(c[j],c[v]+b[j].z);
}
}
for (i=1;i<n;i++)
{
printf("%d ",c[i]);
}
printf("%d\n",c[n]);
return 0;
}
by LYqwq @ 2022-03-01 20:24:01
标准版要加堆优化
by LYqwq @ 2022-03-01 20:24:17
这个 dij 几乎过不了题
by Missa @ 2022-03-01 20:24:19
@Jason12 你的
for (j=a[v];j;j=b[j].x)
会越界
by Missa @ 2022-03-01 20:24:44
另外你dij复杂度不对
by Jason12 @ 2022-03-01 20:33:58
@璇___ @LYqwq 谢谢大佬们!Thanks♪(・ω・)ノ