社区讨论

求解啊 为什么输出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 条回复,欢迎继续交流。

正在加载回复...