社区讨论
求解啊 为什么输出inf?
P1576最小花费参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6h7ks2
- 此快照首次捕获于
- 2025/11/20 04:49 4 个月前
- 此快照最后确认于
- 2025/11/20 04:49 4 个月前
CPP
#include <cstdio>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x7fffffff
const int maxn = 400001;
struct Data{
int to;
double value;
int next;
}edges[1000005];
int first[maxn], que[10000005], vis[maxn];
int N, M, head, tail, start, tot = 0;
double dis[maxn];
inline void addedge(int u, int v, int w){
edges[tot++].to = v;
edges[tot].value = w;
edges[tot].next = first[u];
first[u] = tot;
}
void SPFA(int A, int B){
// for(int i = 1; i <= N; i++) dis[i] = INF;
start = A;
dis[start] = 1;
vis[start] = 1;
que[tail++] = start;
while(head < tail){
int u = que[head++];
vis[u] = 0;
for(int k = first[u]; k; k = edges[k].next){
int v = edges[k].to;
if(dis[v] < dis[u] * edges[k].value){
dis[v] = dis[u] * edges[k].value;
if(!vis[v]){
que[tail++] = v;
vis[v] = 1;
}
}
}
}
}
int main(){
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
cin >> N >> M;
for(int i = 1; i <= M; i++){
int u, v;
double w;
scanf("%d%d%lf", &u, &v, &w);
addedge(u, v, double((100 - w) / 100));
addedge(v, u, double((100 - w) / 100));
}
int A, B;
cin >> A >> B;
SPFA(A, B);
printf("%.8lf",100/double(dis[B]));
return 0;
}
比较裸的一个SPFA 为什么总是输出inf
回复
共 3 条回复,欢迎继续交流。
正在加载回复...