798236606 发表于 2020-2-22 17:16:49

一道图的最短路径问题,大佬帮忙看下

本帖最后由 798236606 于 2020-2-22 17:20 编辑

题目:https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

之前用迪杰斯特拉算法和BF算法成功通过,但是BF算法的优化算法SPFA算法总是有两个点没通过。
看了一下午了,不知道哪里有问题{:10_266:}

C++代码:
#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

const int maxn = 510;

typedef struct node{
    int id, dis;

    node (int _id, int _dis) : id(_id), dis(_dis) {};
}Node;

int n, m, c1, c2;
int weight;//存放点权,即救援队数
int num;//存放到每个点的最短路径数
int w;//存放可聚集的队伍数
int d;//存放最短路径长度
bool inq;//是否在队列内
vector<Node> adj;//邻接表
set<int> pre;//存放顶点在最短路径中的前驱

void SPFA(int s)
{
    fill(d, d + n, INT_MAX);
    memset(w, 0, sizeof(w));
    memset(num, 0, sizeof(num));
    memset(inq, false, sizeof(inq));

    queue<int> q;
    q.push(s);
    w = weight;
    d = 0;
    num = 1;
    inq = true;

    while (!q.empty())
    {
      int u = q.front();
      q.pop();
      inq = false;

      for (int v = 0; v < adj.size(); v++)//遍历u连接的每一条边
      {
            int id = adj.id, dis = adj.dis;

            if (dis + d < d)//如果以u为前驱路径更短
            {
                d = dis + d;
                num = num;
                w = weight + w;
                pre.clear();
                pre.insert(u);

                if (!inq)//如果id不在队列中
                {
                  q.push(id);
                  inq = true;                  
                }
            }
            else if (dis + d == d)//如果存在等价路径
            {
                if (weight + w > w)
                  w = weight + w;

                num = 0;
               
                pre.insert(u);
                for (set<int>::iterator it = pre.begin(); it != pre.end(); ++it)
                  num += num[*it];
            }
      }
    }
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &c1, &c2);

    for (int i = 0; i < n; i++)
      scanf("%d", weight + i);
   
    while (m--)
    {
      int a, b, l;
      scanf("%d %d %d", &a, &b, &l);

      adj.push_back(node(b, l));
      adj.push_back(node(a, l));
    }

    SPFA(c1);

    printf("%d %d", num, w);

    return 0;
}

蒋博文 发表于 2020-2-23 18:05:00

我这里没毛病啊
{:10_277:}

798236606 发表于 2020-2-24 10:11:19

蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊

假的{:10_249:}

蒋博文 发表于 2020-2-24 17:06:13

我只有前两个数据,{:10_261:}

蒋博文 发表于 2020-2-24 17:06:57

显示正确{:10_261:}

798236606 发表于 2020-2-25 11:16:28

蒋博文 发表于 2020-2-24 17:06
我只有前两个数据,

{:10_285:}我不信,你肯定打开方式不对

蒋博文 发表于 2020-2-25 12:13:15

我好像直接用Dev-c++运行了。。。。{:10_277:}

一个账号 发表于 2020-2-25 12:47:38

蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊

骗人:

蒋博文 发表于 2020-2-25 12:48:16

一个账号 发表于 2020-2-25 12:47
骗人:

我都说了,
我好像直接用Dev-c++运行了。。。。

蒋博文 发表于 2020-2-25 12:48:47

蒋博文 发表于 2020-2-25 12:48
我都说了,
我好像直接用Dev-c++运行了。。。。

自己看看,别随便诬陷人
{:10_249:}

wwqq1234054 发表于 2020-2-26 12:47:28

网站收下了{:5_109:}
页: [1]
查看完整版本: 一道图的最短路径问题,大佬帮忙看下