POJ 2387 Til the Cows Come Home （最短路径 模版题 三种解法）

原题链接：Til the Cows Come Home

题目大意：有  个点，给出从  点到  点的距离并且  和  是互相可以抵达的,问从  到  的最短距离。

题目分析：这是一道典型的最短路径模版题，需要注意的是：使用dijkstra算法求解需要考虑有重复边问题，而使用bellman-ford算法 和 spfa算法 可以忽略这个问题。

---

代码如下：

// Dijkstra
#include <iostream>
using namespace std;const int INTFY = 1 << 29;
const int MAX = 1005;
int map[MAX][MAX];
int n,m;void dijkstra() {
int min, v;
int d[MAX];
bool vis[MAX];for(int i = 1; i <= n; i++) {
vis[i] = 0;
d[i] = map[1][i];
}for(int i = 1; i <= n; i++) {
min = INTFY;
for(int j = 1; j <= n; j++)
if(!vis[j] && d[j] < min) {
v = j;
min = d[j];
}
vis[v] = 1;for(int j = 1; j <= n; j++)
if(!vis[j] && d[j] > map[v][j] + d[v])
d[j] = map[v][j] + d[v];
}
cout << d[n] << endl;
}int main() {
int a, b, c;
while(cin >> m >> n) {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i == j)
map[i][i] = 0;
else map[i][j] = map[j][i] = INTFY;for(int i = 1; i <= m; i++) {
cin >> a >> b >> c;
if(map[a][b] > c) map[a][b] = map[b][a] = c;
}
dijkstra();
}
return 0;
}

// Bellman-ford
#include <iostream>
using namespace std;const int INFTY = 1 << 29;
const int MAXM = 2005;
const int MAXV = 1005;typedef struct {
int a, b, w;
}Edge;Edge edge[MAXM];
int n, m;void bellman_ford() {
int d[MAXV];
for(int i = 2; i <= n; i++) d[i] = INFTY;
d[1] = 0;for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(d[edge[j].a] > edge[j].w + d[edge[j].b]) d[edge[j].a] = edge[j].w + d[edge[j].b];
if(d[edge[j].b] > edge[j].w + d[edge[j].a]) d[edge[j].b] = edge[j].w + d[edge[j].a];
}
}
cout << d[n] << endl;
}int main() {
int a, b, c;
while(cin >> m >> n) {
for(int i = 1; i <= m; i++) {
cin >> a >> b >> c;
edge[i].a = a;
edge[i].b = b;
edge[i].w = c;
}
bellman_ford();
}
return 0;
}

// Spfa
#include <iostream>
#include <queue>
using namespace std;const int INFTY = 1 << 29;
const int MAXM = 4005;
const int MAXV = 1005;typedef struct{
int a, b, w, next;
}Edge;Edge edge[MAXM];
int n, m, headlist[MAXV];void spfa() {
int d[MAXV], vis[MAXV];
queue<int> q;
for(int i = 2; i <= n; i++) {
d[i] = INFTY;
vis[i] = 0;
}d[1] = 0;
vis[1] = 1;
q.push(1);while(!q.empty()) {
int v = q.front(); q.pop();
vis[v] = 0;for(int i = headlist[v]; i != -1; i = edge[i].next)
if(d[v] + edge[i].w < d[edge[i].b]) {
d[edge[i].b] = d[v] + edge[i].w;
if(!vis[edge[i].b]) {
vis[edge[i].b] = 1;
q.push(edge[i].b);
}
}
}
cout << d[n] << endl;
}int main() {
int a, b, c;
while(cin >> m >> n) {
for(int i = 1; i <= n; i++) headlist[i] = -1;
for(int i = 1; i <= 2 * m; i += 2) {
cin >> a >> b >> c;
edge[i].a = a;
edge[i].b = b;
edge[i].w = c;
edge[i].next = headlist[a];
headlist[a] = i;
edge[i+1].a = b;
edge[i+1].b = a;
edge[i+1].w = c;
edge[i+1].next = headlist[b];
headlist[b] = i + 1;
}
spfa();
}
return 0;
}