C++ Dijkstra

Question

题目 http://ybt.ssoier.cn:8088/problem_show.php?pid=1381
这里使用的是链式前向星存图
为什么输出是错误的？

#include<iostream>
using namespace std;
const int inf=0x3f3f3f;
struct node
{
    int n,next,w;
} S[10001];
int head[10001],d[10001],v[10001],tot=0,n,m;
void in(int n,int m,int w)
{
    tot++;
    S[tot].n=m;
    S[tot].w=w;
    S[tot].next=head[n];
    head[n]=tot;
}
void F(int x)
{
    for(int i=0; i<=n; i++)
    {
        d[i]=inf;
    }
    d[x]=0;
    for(int l=1; l<=n; l++)
    {
        int u=0;
        for(int i=1; i<=n; i++)
        {
            if(d[i]<d[u] && v[i]==0)
            {
                u=i;
            }
        }
        v[u]=1;
        for(int i=head[x]; S[i].n!=0; i=S[i].next)
        {
            if(d[u]+S[i].w<d[i])
            {
                d[i]=d[u]+S[i].w;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        in(x,y,w);
    }
    F(1);
    cout<<d[n];
}

Answer 1

【以下回答由 GPT 生成】

原因分析： 1. 在链式前向星存图的实现中，代码中的head[x]应该是head[u]，因为要遍历以u为起点的所有边。这是一个拼写错误。

解决方案： 将代码中的head[x]改为head[u]。

优化错误输出： 修改代码中的输出语句，当d[n]为inf时，输出"无法到达"。

修改后的代码如下：

#include<iostream>
using namespace std;
const int inf=0x3f3f3f;
struct node
{
    int n,next,w;
} S[10001];
int head[10001],d[10001],v[10001],tot=0,n,m;
void in(int n,int m,int w)
{
    tot++;
    S[tot].n=m;
    S[tot].w=w;
    S[tot].next=head[n];
    head[n]=tot;
}
void F(int x)
{
    for(int i=0; i<=n; i++)
    {
        d[i]=inf;
    }
    d[x]=0;
    for(int l=1; l<=n; l++)
    {
        int u=0;
        for(int i=1; i<=n; i++)
        {
            if(d[i]<d[u] && v[i]==0)
            {
                u=i;
            }
        }
        v[u]=1;
        for(int i=head[u]; S[i].n!=0; i=S[i].next)
        {
            if(d[u]+S[i].w<d[S[i].n])
            {
                d[S[i].n]=d[u]+S[i].w;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        in(x,y,w);
    }
    F(1);
    if(d[n]==inf)
    {
        cout<<"无法到达";
    }
    else
    {
        cout<<d[n];
    }
}

请注意：这只是一种可能的解决方案，可能还存在其他错误或优化点。如果这个解决方案不能解决您的问题，请提供更多的信息。

【相关推荐】

• 这篇文章：基于C++的Dijkstra最短路径算法 也许能够解决你的问题，你可以看下
• 除此之外, 这篇博客: C++Dijkstra算法求最短路径中的 我的浅显理解 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^