一道图的最短路径问题,大佬帮忙看下
本帖最后由 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;
} 我这里没毛病啊
{:10_277:} 蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊
假的{:10_249:}
我只有前两个数据,{:10_261:} 显示正确{:10_261:} 蒋博文 发表于 2020-2-24 17:06
我只有前两个数据,
{:10_285:}我不信,你肯定打开方式不对 我好像直接用Dev-c++运行了。。。。{:10_277:}
蒋博文 发表于 2020-2-23 18:05
我这里没毛病啊
骗人:
一个账号 发表于 2020-2-25 12:47
骗人:
我都说了,
我好像直接用Dev-c++运行了。。。。
蒋博文 发表于 2020-2-25 12:48
我都说了,
我好像直接用Dev-c++运行了。。。。
自己看看,别随便诬陷人
{:10_249:} 网站收下了{:5_109:}
页:
[1]