首页 > ACM题库 > HDU-杭电 > hdu 2544 最短路-最短路径-[解题报告]C++
2014
02-10

hdu 2544 最短路-最短路径-[解题报告]C++

最短路

问题描述 :

在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

输入:

输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

输出:

输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

样例输入:

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

样例输出:

3
2

题意,赤果果的最短路

想当年傻傻地用floyd和dijkstra乱刷过,最近好好理解了一下最短路,今天用四种算法实现了一遍。

以后可以当模板用。

代码:

floyd

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        hdu2544.cpp
*  Create Date: 2013-11-28 15:37:26
*  Descripton:  min path, floyd
*/

#include <cstdio>
#include <cstring>

const int MAXN = 110;
const int INF = 0x3c3c3c3c - 1;

int nn, en;	// num of node and edge
int map[MAXN][MAXN];

int min(int a, int b) {
	return a < b ? a : b;
}

int floyd() {
	for (int k = 1; k <= nn; k++)
		for (int i = 1; i <= nn; i++)
			for (int j = 1; j <= nn; j++)
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}

int main() {
	int s, e, t;
	while (~scanf("%d%d", &nn, &en) && (nn || en)) {
		// init
		for (int i = 1; i <= nn; i++)
			for (int j = 1; j <= nn; j++)
				map[i][j] = INF;
		// input
		for (int i = 0; i < en; i++) {
			scanf("%d%d%d", &s, &e, &t);
			if (t < map[s][e])
				map[s][e] = map[e][s] = t;
		}
		floyd();
		printf("%d\n", map[1][nn]);
	}
	return 0;
}

dijkstra

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        hdu2544.cpp
*  Create Date: 2013-11-28 15:37:26
*  Descripton:  min path, dijkstra
*/

#include <cstdio>
#include <cstring>

const int MAXN = 110;
const int INF = 0x3c3c3c3c - 1;

int nn, en;	// num of node and edge
int map[MAXN][MAXN], dis[MAXN];
bool vis[MAXN];

int dijkstra(int s, int e) {
	memset(vis, 0, sizeof(vis));
	// init the dis
	for (int i = 1; i <= nn; i++)
		if (i == s) dis[i] = 0;
		else dis[i] = map[s][i];
	vis[s] = true;
	for (int i = 1; i <= nn; i++) {
		int t = INF, k;
		for (int j = 1; j <= nn; j++)
			if (!vis[j] && t > dis[j])
				t = dis[j], k = j;
		if (t == INF) break;
		vis[k] = true;
		for (int j = 1; j <= nn; j++)
			if (!vis[j] && dis[j] > dis[k] + map[k][j])
				dis[j] = dis[k] + map[k][j];
	}
	return dis[e];
}

int main() {
	int s, e, t;
	while (~scanf("%d%d", &nn, &en) && (nn || en)) {
		// init
		for (int i = 1; i <= nn; i++)
			for (int j = 1; j <= nn; j++)
				map[i][j] = INF;
		// input
		for (int i = 0; i < en; i++) {
			scanf("%d%d%d", &s, &e, &t);
			if (t < map[s][e])
				map[s][e] = map[e][s] = t;
		}
		printf("%d\n", dijkstra(1, nn));
	}
	return 0;
}

bellman ford

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        hdu2544.cpp
*  Create Date: 2013-11-28 15:37:26
*  Descripton:  min path, bellman ford 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 110;
const int INF = 0x3c3c3c3c - 1;

struct Edge {
	int u, v;
	int cost;
} e[MAXN * MAXN / 2];

int nn, en;	// num of node and edge
int dis[MAXN];

int bellman_ford(int op, int ed) {
	for (int i = 1; i <= nn; i++)
		dis[i] = INF;
	dis[op] = 0;
	for (int i = 0; i < nn - 1; i++)
		for (int j = 0; j < en * 2; j++)
			dis[e[j].v] = min(dis[e[j].v], dis[e[j].u] + e[j].cost);
	return dis[ed];
}

int main() {
	int op, ed, t;
	while (~scanf("%d%d", &nn, &en) && (nn || en)) {
		// input
		for (int i = 0; i < en; i++) {
			scanf("%d%d%d", &op, &ed, &t);
			e[i].u = op; e[i].v = ed; e[i].cost = t;
			e[i + en].u = ed; e[i + en].v = op; e[i + en].cost = t;
		}
		printf("%d\n", bellman_ford(1, nn));
	}
	return 0;
}

spfa+queue

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        hdu2544.cpp
*  Create Date: 2013-11-28 15:37:26
*  Descripton:  min path, spfa
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;

const int MAXN = 110;
const int INF = 0x3c3c3c3c - 1;

int nn, en;	// num of node and edge
int map[MAXN][MAXN], dis[MAXN];
bool vis[MAXN]; // if in the queue

int spfa(int op, int ed) {
	queue<int> q;
	memset(vis, false, sizeof(vis));

	for (int i = 1; i <= nn; i++)
		dis[i] = INF;
	dis[op] = 0;

	q.push(op);
	vis[op] = true;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		vis[cur] = false;
		for (int i = 1; i <= nn; i++)
			if (dis[i] > dis[cur] + map[cur][i]) {
				dis[i] = dis[cur] + map[cur][i];
				if (!vis[i]) {
					q.push(i);
					vis[i] = true;
				}
			}
	}
	return dis[ed];
}

int main() {
	int op, ed, t;
	while (~scanf("%d%d", &nn, &en) && (nn || en)) {
		// init
		for (int i = 1; i <= nn; i++)
			for (int j = 1; j <= nn; j++)
				map[i][j] = INF;
		// input
		for (int i = 0; i < en; i++) {
			scanf("%d%d%d", &op, &ed, &t);
			if (t < map[op][ed])
				map[op][ed] = map[ed][op] = t;
		}
		printf("%d\n", spfa(1, nn));
	}
	return 0;
}

解题转自:http://blog.csdn.net/hcbbt/article/details/17008877


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮