社区讨论

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 条回复,欢迎继续交流。

正在加载回复...