A1030 Travel Plan (30分)

一、技术总结

1. 这一题是关于图的遍历，但是涉及Djikstra算法，在求最短路径的同时，还要把路径记录下来；同时增加了边权，也就会每个城市之间的花费；
2. 这里采用Djikstra算法+DFS遍历的方法
3. 第一步使用Djikstra算法求出最短路径，使用vector类型pre数组进行存储，每个结点里面保存的是他们的前驱结点。
4. 然后再使用DFS遍历pre，然后会有得出遍历树。
5. 要注意下标是0_{n-1，还是1}n。
6. 细节问题参考代码

二、参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int INF = 100000000;
bool vis[MAXN] = {false};
int d[MAXN], c[MAXN];
int G[MAXN][MAXN], cost[MAXN][MAXN];
vector<int> pre[MAXN];
vector<int> path, tempPath;
int n, m, c1, c2;//求的两城市id号 
int optValue = INF;
void Djikstra(int s){
	fill(d, d+MAXN, INF);
	d[s] = 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);
				}
			}
		}
	}
}
void DFS(int v){
	if(v == c1){

		tempPath.push_back(v);
		int value = 0;
		for(int i = tempPath.size()-1; i > 0; i--){
			int id = tempPath[i], idNext = tempPath[i-1];
			value += cost[id][idNext]; 
		}
		if(value < optValue){
			path = tempPath;
			optValue = value;
		}
		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, &c1, &c2);
	int id1, id2;
	int distance, price;
	fill(G[0], G[0]+MAXN*MAXN, INF);
	fill(cost[0], cost[0]+MAXN*MAXN, INF);
	for(int i = 0; i < m; i++){
		scanf("%d%d%d%d", &id1, &id2, &distance, &price);
		G[id1][id2] = distance;
		G[id2][id1] = distance;
		cost[id1][id2] = price;
		cost[id2][id1] = price;
	}
	Djikstra(c1);
	DFS(c2);
	for(int i = path.size()-1; i >= 0; i--){
		printf("%d ", path[i]);
	}
	printf("%d %d", d[c2], optValue);
	return 0;
}