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

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

题目分析：这是一道典型的最短路径模版题，需要注意的是：使用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;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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