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;
}
