1018 Public Bike Management （30 分）

因为是无向图，所以给边赋值的时候，就直接粘贴了，但是没有改变两个端点了位置，调试了一下午，终于找到问题原因了，可喜可贺，可歌可泣。
其实代码写得清晰明了一些，可以节约大量的时间呀！

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=505;
const int INF=1e9+5;
int C,N,D,M; //C为每个站的最大容量，N个站点，D为终点，M条路； 
int G[maxn][maxn]; //耗时 
int d[maxn]; //耗时最短
bool vis[maxn]={false}; 
int dot[maxn];
vector<int> pre[maxn];
void Dijkstra(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	for(int i=0;i<=N;i++){ //n个顶点 
		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(G[u][v] + d[u] < d[v]){
					d[v]=G[u][v] + d[u];
					pre[v].clear();
					pre[v].push_back(u); //把u设为前驱节点 
				}else if(G[u][v] + d[u] == d[v]){
					pre[v].push_back(u); //直接加在v的后面，表示还有另一个前驱 
				} 
			}
		}
	}
	
}
int optN=INF,optT=INF; //最小发送车辆和最小带回车辆 
vector<int> path,tempPath;
void DFS(int v) {
	if(v==0){
		tempPath.push_back(0);
		int value=0,temp=0,tempN=0,tempT=0;
		dot[0]=C; 
		for(int i=tempPath.size()-1;i>=0;i--){ //从PBMC出发 
			int id=tempPath[i];
			 	temp+=dot[id]-C;
			if(temp < 0){
				tempN += (-temp);
				temp=0;
			}
		}
		if(temp > 0)  tempT = temp; 
		if(tempN < optN ){
			optT=tempT;
			optN=tempN;
			path=tempPath;
		}else if(tempN == optN && tempT < optT){
			optT=tempT;
			optN=tempN;
			path=tempPath;
		}
		tempPath.pop_back();
		return;	
	}
	tempPath.push_back(v);
	for(int j=0;j<pre[v].size();j++){
		DFS(pre[v][j]);
	}
	tempPath.pop_back();
}
int main(){
	scanf("%d%d%d%d",&C,&N,&D,&M);
	int x,y,cost;
	C = C>>1; 
	fill(G[0],G[0]+maxn*maxn,INF);
	for(int i=1;i<=N;i++){
		scanf("%d",&dot[i]);
	}
	
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&x,&y,&cost);
		G[x][y]=cost;  //为无向图 
		G[y][x]=cost;
	} 
	Dijkstra(0);
	DFS(D); 
	
	printf("%d ",optN);
	for(int i=path.size()-1;i>=0;i--){
		printf(i==0?"%d":"%d->",path[i]);
	}
	printf(" %d\n",optT);
	return 0;
}