HDOJ 2544 最短路

http://acm.hdu.edu.cn/showproblem.php?pid=2544

题面：
最短路裸题。

Bellman-Ford算法：

//  Bellman-Ford最短路算法
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define MAX_V 105
#define MAX_E 10005
#define INF 0x3f3f3f3f
using namespace std;

struct edge {
    int from, to;
    int cost;
};
edge g[MAX_E];
int d[MAX_V]; // d[i]表示d[start]到i点的最短距离
int v, e; // 顶点数， 边数
int start, to;

void Bellman_Ford(int s) {
    for (int i = 1; i <= v; ++i)
        d[i] = INF;
    d[s] = 0;
    bool update = true;
    while (update) {
        update = false;
        for (int i = 1; i <= 2 * e; ++i) {
            edge e = g[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
    }
}
int main() {
    while (cin >> v >> e && v && e) {
        for (int i = 1; i <= e; ++i) {
            int f, t, c;
            cin >> f >> t >> c;
            g[i].from = g[i + e].to = f;
            g[i].to = g[i + e].from = t;
            g[i].cost = g[i + e].cost = c;
        }
        Bellman_Ford(1);
        cout << d[v] << '\n';
    }
    return 0;
}