1030. Travel Plan 解析

直接Dijstra感觉简单点，这个第二标尺比较容易想明白。Dijstra+DFS感觉反而麻烦了一点 两个都写了下练练手。

#include <iostream>#include <string>#include <vector>#include <algorithm>#include <climits>#include <stack>#define MAX 510using namespace std;struct Node {	int v;	int dis;	int cost;};vector <Node> g[MAX];vector <bool> isVis;vector <int> PRe[MAX];vector <int> dis;vector <int> cost;int P[MAX];int C[MAX];int N, M, S, D;void dijstra(int st) { //st 起点		dis[st] = 0;	C[st] = 0;	for (int i = 0; i < N; i++) {				int min = INT_MAX, u = -1;		for (int j = 0;j < N; j++) { //找最小距离			if (!isVis[j] && min > dis[j]) {				min = dis[j];				u = j;			}		}		if (u == -1) return;//没有最小值		isVis[u] = true;		for (int j = 0; j < g[u].size(); j++) {			int v = g[u][j].v;			if (!isVis[v]) {				if (dis[v] > dis[u] + g[u][j].dis) {					dis[v] = dis[u] + g[u][j].dis;					pre[v].clear();					pre[v].push_back(u);					//法二					P[v] = u;					C[v] = C[u] + g[u][j].cost;				}				else if (dis[v] == dis[u] + g[u][j].dis) {					pre[v].push_back(u);					//法二					if (C[v] > C[u] + g[u][j].cost) {						P[v] = u;						C[v] = C[u] + g[u][j].cost;					}				}			}		}	}}vector <int> patch, ThisPath;int MinCost = INT_MAX;void DFS(int v) {	if (v == S) { //到达起点		ThisPath.push_back(v);		int ThisCost = 0;		int ID = 0;		int IDN = 0;		for (int i = ThisPath.size() - 1; i > 0; i--) {			ID = ThisPath[i];			IDN = ThisPath[i - 1];			for (int j = 0; j < g[ID].size(); j++) {				if (g[ID][j].v == IDN)					IDN = j;			}			ThisCost += g[ID][IDN].cost;		}		if (ThisCost < MinCost) {			MinCost = ThisCost;			patch = ThisPath;		}		ThisPath.pop_back();		return;	}	ThisPath.push_back(v);	for (int i = 0; i < pre[v].size(); i++) {		DFS(pre[v][i]);	}	ThisPath.pop_back();	}int main() {	cin >> N >> M >> S >> D;	isVis.resize(N, false);	dis.resize(N,INT_MAX);	cost.resize(N, INT_MAX);		for (int i = 0; i < N; i++) {		C[i] = INT_MAX;		P[i] = -1;	}	int Head, Tail;	Node temp;	for (int i = 0; i < M; i++) {		cin >> Head >> Tail >> temp.dis >> temp.cost;		temp.v = Tail;		g[Head].push_back(temp);		temp.v = Head;		g[Tail].push_back(temp);	}#ifdef _DEBUG	for (int i = 0; i < N; i++) {			for (int j = 0; j < g[i].size(); j++) {		 	cout <<i << " " <<  g[i][j].v << " dis:" << g[i][j].dis << " cost:" << g[i][j].cost << endl;		}	}#endif	//法一	dijstra(S);	DFS(D);	for (int i = patch.size() - 1; i >= 0; i--) {		cout << patch[i] << " ";	}	cout << dis[D] << " " << MinCost << endl;#ifdef _DEBUG	for (int i = 0; i < N; i++) {		cout << "-------" << i << "--------" << endl;		for (int j = 0; j < pre[i].size(); j++) {			cout << pre[i][j] << endl;		}	}#endif			//法二	//stack <int> s;	//int p = D;	//while (p != -1) {	//	s.push(p);	//	p = P[p];	//}	//while (!s.empty()) {	//	cout << s.top() << " ";	//	s.pop();	//}	//cout << dis[D] << " " << C[D] << endl;	system("pause");	return 0;}