1018. Public Bike Management 解析

单用Dijstra算法比较难维护。用Dijstra+DFS能简化不少。

看到有小伙伴例7有问题，可以看下是不是Dijstra的算法在计算路径的时候出问题没。我的就是下标u和i弄混了。查了好久。。。。。

#include <iostream>#include <vector>#include <string>#include <climits>#include <stack>using namespace std;struct Node {	int length;	int Num;};struct Grap {	int bIkeNum;	vector <Node> link;};void Dijkstra(Grap * g, int * dis ,vector<int> * PRe ,int N,bool * isvisit ) {	dis[0] = 0;	for (int i = 0; i < N; i++) {		int u = -1, Min = INT_MAX;		for (int j = 0; j < N; j++) { //找Dis最小值			if (!isvisit[j] && dis[j] < Min) {				u = j;				Min = dis[j];			}		}		if (u == -1) return;		isvisit[u] = true;				for (int j = 0; j < g[u].link.size(); j++) {			int v = g[u].link[j].Num;			if (!isvisit[v]) {				if (dis[u] + g[u].link[j].length < dis[v]) {//u是中间结点					pre[v].clear();					pre[v].push_back(u);					dis[v] = dis[u] + g[u].link[j].length;				}				else if (dis[u] + g[i].link[j].length == dis[v]) {					pre[v].push_back(u);				}			}		}	}}void DFS(vector <int> * pre, vector <int> & patch, vector <int> & tempatch, Grap * g, int & BikeNeed, int & BikeReturn, int v, int Cmax) {	//cout << " v = " << v << endl;	int perfect = Cmax / 2;	if (v == 0) {		tempatch.push_back(v);		int bn = 0, br = 0;		//计算大小		//cout << "size: " << tempatch.size() << endl;		for (int i = tempatch.size() - 1; i >= 0; i--) {			int b = g[tempatch[i]].bIkeNum;			if (b > perfect) {//大于perfect需要带走				br += b - perfect;			}			else if (b < perfect){ //补齐				br -= (perfect - b);	//			cout << "br : " << br <<  endl;				if (br < 0) {//不够补齐 要从中心调					bn += (-br);					br = 0;				}			}		}		//判断		if (bn < BikeNeed) {			BikeNeed = bn;			BikeReturn = br;			patch = tempatch;		}		else if (bn == BikeNeed && br < BikeReturn) {			BikeNeed = bn;			BikeReturn = br;			patch = tempatch;		}		tempatch.pop_back();				return;	}	tempatch.push_back(v);	for (int i = 0; i < pre[v].size(); i++) {		DFS(pre, patch, tempatch, g, BikeNeed, BikeReturn, pre[v][i], Cmax);	}	tempatch.pop_back();}int main() {	int Cmax, N, SP, M;	//Cmax最大容量，N站总数，SP问题站编号，M道路总数	cin >> Cmax >> N >> SP >> M;	Grap * g = new Grap[N + 1];	stack <int> s;	for (int i = 1; i <= N; i++) {		cin >> g[i].bIkeNum;	}	g[0].bIkeNum = Cmax / 2;	Node tempNode;	int tempHead, tempTail;	for (int i = 0; i < M; i++) {		cin >> tempHead >> tempTail >> tempNode.length;		tempNode.Num = tempTail;		g[tempHead].link.push_back(tempNode);		//cout << tempHead << " " << tempNode.Num << " " << tempNode.length << endl;		tempNode.Num = tempHead;		g[tempTail].link.push_back(tempNode);		//cout << tempTail << " " << tempNode.Num << " " << tempNode.length << endl;	}//	int MinLegnth = INT_MAX;	bool * isVisit = new bool[N + 1];	int * dis = new int[N + 1];	vector <int> * pre = new vector<int>[N + 1];	for (int i = 0; i <= N; i++) {		dis[i] = INT_MAX;		isVisit[i] = false;	}	Dijkstra(g, dis, pre, N + 1, isVisit);	int BikeNeed = INT_MAX, BikeReturn = INT_MAX;	vector <int> patch, tempatch;	DFS(pre, patch, tempatch, g, BikeNeed, BikeReturn, SP, Cmax);	cout << BikeNeed << " ";	for (int i = patch.size() - 1; i > 0; i--) {		cout << patch[i] << "->";	}	cout << patch[0] << " ";	cout << BikeReturn << endl;	system("pause"); 	return 0;}