PAT 甲级 A1030 Travel Plan

A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Sample Output:

0 2 3 3 40

题意：

n个结点（4）， m条边（5），起点是st（0），终点是ed（3），再给出两个城市的距离和路途花费，求最短路径的同时最短花费；

代码：

①本质路上的花费和路程是一样的，都是两点的边权，所以可以计算最有距离的时候，进行最少花费的优化，即当最小距离改变的时候，重新初始化花费，如果最小路径相同的情况下，再进行优化判断；

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1010;
const int INF = 1 << 30 -1;
int n, m, st, ed;
int G[maxn][maxn], cost[maxn][maxn];//两个边权，距离和花费; 
int d[maxn], c[maxn];//起点到某个点的最短距离， 起点到某个点的最小花费; 
int pre[maxn];//存放最短路径的各个顶点的前驱结点;
bool vis[maxn] = {false};

//Dijkstra算出最短路径， 最小距离， 最小花费; 
void Dijkstra(int st) {
	fill(d, d+maxn, INF);//点权边权都要初始化为INF，为优化作准备; 
	fill(c, c+maxn, INF);
	//标准初始化; 
	
	for(int i = 0; i < n; i++) pre[i] = i;//初始化pre数组,当图都不连通的时候，起码有起点自己指向自己; 
	d[st] = 0; 
	c[st] = 0;
	for(int i = 0; i < n; i++) {//保证遍历到每个顶点; 
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++) {//找到未访问最短距离出边,即目前最优子结构; 
			if(vis[j] == false && d[j] < MIN) {
				u = j;
				MIN = d[j]; 
			}	
		}
		if(u == -1) return ;
		vis[u] = true;//去到城市u； 
		for(int v = 0; v < n; v++) {//优化u的邻居; 
			if(vis[v] == false && G[u][v] != INF) {
				//我u去你哪里比较近; 
				if(d[u] + G[u][v] < d[v]) {
					d[v] = d[u] + G[u][v];
					c[v] = c[u] + cost[u][v];
					pre[v] = u;//记录其前驱结点,然后就可以从结尾找到起点，从而找出最短路径; 
					//因为只有起点有最小距离是自己到自己的特点，这个作为递归边界，所以只能从结尾往前递归； 
				}else if(d[u] + G[u][v] == d[v]) {
					if(c[u] + cost[u][v] < c[v]) {
						c[v] = c[u] + cost[u][v];
						pre[v] = u;	
					}
				}
			}
		} 
		
	}
	
}

void DFS(int v) {
	if(v == st) {
		printf("%d ", v);
		return ;
	}
		DFS(pre[v]);//递归其前驱结点，从而找到根节点 
		printf("%d ", v);//回溯输出;

}



int main () {
	scanf("%d %d %d %d", &n, &m, &st, &ed);
	fill(G[0], G[0]+maxn*maxn, INF);//二维数组的初始化，以此限制出边,用于判断各点是否连通：  
	for(int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		scanf("%d", &G[u][v]);
		G[v][u] = G[u][v];
		scanf("%d", &cost[u][v]);
		cost[v][u] = cost[u][v];
	}//建图;
	
	Dijkstra(st);
	DFS(ed);//pre是按从终点到起点存放的；
	printf("%d %d", d[ed], c[ed]); 
	return 0; 
}

②Dijstra只负责找出最短路径，DFS遍历最短路径树，从而在所有路径中找到满足最小花费的路径

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int INF = 1 << 30 - 1;
const int maxn =1010;
int n, m, st, ed;
int G[maxn][maxn], cost[maxn][maxn];
int d[maxn];
bool vis[maxn] = {false};
vector<int> pre[maxn];//建造路径的递归数; 
void Dijkstra(int st) {//Dijkstra算法只用于找最短路径;
	fill(d, d + maxn, INF); //为后面优化作准备; 
	d[st] = 0;
	for(int i = 0; i < n; i++) { 
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++) {//找到最优解子结构; 
			if(vis[j] == false && d[j] < MIN) {
				u = j;
				MIN = d[j];
			}
		}
		if(u == -1) return ;//找不到最有子结构，都已经是最优解了;
		vis[u] = true;
		for(int v = 0; v < n; v++) {
			if(vis[v] == false && G[u][v] != INF) {
				if(d[u] + G[u][v] < d[v]) {
					d[v] = d[u] + G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				}else if(d[u] + G[u][v] == d[v]) {
					pre[v].push_back(u);
				}
			}
		}
	}
}
//找出最短路径;
vector<int > path, tempPath;
int mincost = INF;

void DFS(int v) {//深度优先搜索遍历所有路径找到满足第二标尺的路径; 
	if(v == st) {//递归边界,到起点了就说明满一条路径了，算出其第二标尺; 
		tempPath.push_back(v);//不要忘了叶子结点; 
		int tempcost = 0; 
		for(int i = tempPath.size() - 1; i > 0; i--) {//倒着访问，就是从叶子结点到终点； 
			int v = tempPath[i], u = tempPath[i - 1]; 
			tempcost += cost[v][u];
		}
		if(tempcost < mincost) {
			mincost = tempcost;
			path = tempPath;
		}
		tempPath.pop_back();//将叶子结点拿出来，不影响下一个叶子结点的进入;
		return ;//这一层就就结束了， 不能再往下遍历， 等待下一个叶子结点的进入; 
	}
	tempPath.push_back(v);//不到叶子结点就将中间结点放入; 
	for(int i = 0; i < pre[v].size(); i++) {//递归式; 
		DFS(pre[v][i]);//深度优先搜索; 
	}
	tempPath.pop_back();
} 



int main() {
	scanf("%d %d %d %d", &n, &m, &st, &ed);
	fill(G[0], G[0] + maxn*maxn, INF);//矩阵初始化，用于判断结点是否连通;

	for(int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		scanf("%d %d", &G[u][v], &cost[u][v]);
		G[v][u] = G[u][v];
		cost[v][u] = cost[u][v];//无向图; 
	}//建图的过程;
	Dijkstra(st);

	DFS(ed);
	for(int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
	printf("%d %d", d[ed], mincost);;
	return 0;
}