社区讨论
40分,大佬求差错,哪里没有考虑到?
P3371【模板】单源最短路径(弱化版)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6m9atu
- 此快照首次捕获于
- 2025/11/20 07:11 4 个月前
- 此快照最后确认于
- 2025/11/20 07:11 4 个月前
##很朴素的,但是提交之后五颜六色的方块,很迷,求大佬看
CPP#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=500500;
const int inf=2147483647;
int Head[maxn],Next[maxm];
int Q[maxn],V[maxn];
int top=0;
struct node{int x,y,w;}E[maxn];
int D[maxn];
void ins(int x,int y,int w,int i)
{
E[i].y=y;
E[i].w=w;
Next[i]=Head[x];
Head[x]=i;
}
void spfa(int x)
{
Q[++top]=x;
V[x]=true;
while(top)
{
int s=Q[top--];
V[s]=false;
for(int p=Head[s];p;p=Next[p])
{
int y=E[p].y;
int t=D[s]+E[p].w;
if(t<D[y])
{
D[y]=t;
if(!V[y])
{
Q[++top]=y;
V[y]=true;
}
}
}
}
}
int main()
{
int n,m,x;
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
ins(a,b,w,i);
}
for(int i=1;i<=n;i++)
{
if(i!=x)D[i]=inf;
else D[i]=0;
}
spfa(x);
for(int i=1;i<n;i++)
cout<<D[i]<<" ";
cout<<D[n];
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...