为什么我的输出不对？(语言-c++)

Question

为什么我的输出不对？

一张n个点m条边的有向图,每条边的权值相同.你要找4个点a,b,c,d,使得a->b->c->d的最短路最长(a,b,c,d之间要有路),输出一组解.
原输入：
8 9
1 2
2 3
3 4
4 1
4 5
5 6
6 7
7 8
8 5
原输出：2 1 8 7
我的输出：5 1 8 6

#include<bits/stdc++.h>
using namespace std;
#define N 10100
typedef pair<int,int> P;
struct node
{
    int u,v;
}e[N];
vector<P> a[N],b[N];
int n,m,h[N],cnt=0,dis[N][N];
bool cmp(P a,P b)
{
    return a.first>b.first;
}
void add(int u,int v)
{
    cnt++;
    e[cnt].v=v;
    e[cnt].u=h[u];
    h[u]=cnt;
}
queue<int> q;
void bfs(int x)
{
    while(!q.empty())
    {
        int a=q.front();
        q.pop();
        for(int i=h[a];i;i=e[i].u)
        {
            int v=e[i].v;
            if(dis[x][a]+1<=dis[x][v])
            {
                dis[x][v]=dis[x][a]+1;
                q.push(v);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    memset(dis,0x3f3f3f3f,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        dis[i][i]=0;
        q.push(i);
        bfs(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((dis[i][j]==0x3f3f3f3f)||(i==j))
                dis[i][j]=-1;
            if(dis[i][j]!=-1)   a[i].push_back(make_pair(dis[i][j],j));
            if(dis[j][i]!=-1)   b[i].push_back(make_pair(dis[j][i],j));
        }
        sort(a[i].begin(),a[i].end(),cmp);
        sort(b[i].begin(),b[i].end(),cmp);
    }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=n;j++)
    //             cout<<dis[i][j]<<" ";
    //     cout<<"\n";
    // }
    
    int ans=0,f1,f2,f3,f4;
    for(int x2=1;x2<=n;x2++)
    {
        for(int x3=1;x3<=n;x3++)
        {
            if(dis[x2][x3]==-1||x2==x3)//||dis[x3][x2])顺序是由2到3
                continue;
            for(int k1=0;k1<3 && k1<b[x2].size();k1++)
            {   
                int x1=b[x2][k1].second;
                if(x1==x2||x1==x3)
                    continue;
                int w1=b[x2][k1].first;
                for(int k4=1;k4<3 && k4<a[x3].size();k4++)
                {
                    int x4=a[x3][k4].second;
                    if(x4==x1||x4==x2||x4==x3)
                        continue;
                    int w4=a[x3][k4].first;
                    if(dis[x2][x3]+w1+w4>ans)
                    {
                        f1=x1;f2=x2;f3=x3;f4=x4;
                        ans=dis[x2][x3]+w1+w4;
                    }
                }
            }
        }
    }
    cout<<f1<<" "<<f2<<" "<<f3<<" "<<f4<<"\n";
}

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

从您提供的代码和问题描述来看，您的目标是在有向图中找到四个节点a, b, c, d，使得a->b->c->d的最短路径长度最长。让我们逐步分析您的代码，找出可能的问题并提出解决方案。

1. 理解问题：问题已经理解清楚，目标是找到最长的四节点路径。

2. 分析现有代码：

   • 您的代码定义了一个结构体node和全局数组e，a，b，h，dis等，用于存储图的结构和计算结果。
   • 使用add函数构建邻接表，但似乎没有正确地为每个节点初始化邻接表，这可能导致未定义行为。

3. 检查输入处理：

   • 输入处理部分看起来是正确的，但需要确保add函数正确地构建了图。

4. 检查图的遍历：

   • bfs函数实现似乎有逻辑错误。bfs应该从每个节点开始执行，而不是只执行一次。此外，dis[x][a]+1<=dis[x][v]这个条件似乎不正确，应该是dis[x][a]+1 < dis[x][v]。

5. 检查路径选择逻辑：

   • 路径选择逻辑部分存在问题。您需要确保a和b数组正确地存储了从每个节点出发的最长和次长路径。此外，循环的边界条件可能不正确，需要调整以确保所有可能的组合都被考虑。

6. 优化代码：

   • 代码中存在一些未使用的变量和可能的冗余计算。

7. 添加边界条件检查：

   • 需要添加检查以确保图中至少有4个节点。

8. 测试代码：

   • 您应该使用不同的测试用例来验证代码的正确性。

9. 调试和修复：

   • 根据测试结果，使用调试工具和技术来定位并修复问题。

10. 编写清晰的注释：

    • 代码注释需要添加，以提高可读性和可维护性。

11. 最终验证：

    • 在完成所有修复和优化后，重新运行测试用例，确保代码现在能够产生正确的输出。

以下是针对上述分析的一些具体修改建议：

• 确保每个节点的邻接表在main函数中被正确初始化。
• 修改bfs函数，使其从每个节点开始执行，并使用正确的条件来更新dis数组。
• 调整路径选择逻辑，确保正确地选择最长路径。
• 优化代码，移除未使用的变量和冗余计算。
• 添加边界条件检查，确保至少有4个节点。

由于代码修改可能涉及多个部分，这里提供一个修改后的bfs函数作为示例：

void bfs(int x) {
    fill(dis[x], dis[x] + n + 1, 0x3f3f3f3f);
    dis[x][x] = 0;
    q.push(x);
    while (!q.empty()) {
        int a = q.front();
        q.pop();
        for (int i = h[a]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[x][a] + 1 < dis[x][v]) {
                dis[x][v] = dis[x][a] + 1;
                q.push(v);
            }
        }
    }
}

请注意，这只是一个示例，您可能需要根据实际情况调整其他部分的代码。希望这些建议能帮助您解决问题。