大佬们求救啊!(Bellman-Ford算法)
  • 板块学术版
  • 楼主TheFreakOne
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/1/27 19:17
  • 上次更新2023/11/5 04:17:33
查看原帖
大佬们求救啊!(Bellman-Ford算法)
468614
TheFreakOne楼主2021/1/27 19:17
#include<iostream>
#include<cstdio>

using namespace std;

struct edge { int from , to, cost;};

long long INF = 1000000000000;

void shortest_path(int s){
    int V , E;
    cin >> V >> E;

    int MAX_V = V - 1;
    int MAX_E = E - 1;

    edge es[MAX_E];
    for(int i = 0 ; i <= MAX_E ; i++){
        cin >> es[i].from >> es[i].to >> es[i].cost;
    }

    int d[MAX_V];
    for(int i = 0 ; i <= MAX_V ; i++){
        d[i] = INF;
    }
    d[s] = 0;

    while(true){
        bool update = false;
        for(int i = 0 ; i <= MAX_E ; i++){
            edge e = es[i];
            if(d[e.from - 1] != INF && d[e.to - 1] > d[e.from - 1] + e.cost){
                cout << d[e.to -1] << " " << d[e.from -1] << " " << e.cost << endl;
                d[e.to - 1] = d[e.from - 1] + e.cost;
                update = true;
                cout << d[e.to -1] << " " << d[e.from -1] << " " << e.cost << endl;
            }
        }
        if (!update) break;
    }
    for(int i = 0 ;i <= MAX_V ; i++){
        cout << d[i] << endl;
    }
}

int main(){
    int s;
    cin >> s;
    shortest_path(s - 1);

    return 0;
}

请问这有什么不对吗,为什么测试结果问题很大啊???

2021/1/27 19:17
加载中...