pat 1018

题目描述：

给一张图, 每个node都代表一个杭州的一个借或者还自行车站点, node上的值表示当前这个站点拥有多少量自行车, 每条边表示两个站点之间要花多少时间从一个站点到另一个站点, 给定一个有问题的站点, 求出从控制中心(PBMC)到该站点的最短路径并且使得带出去以及拿回来的自行车的数量最少.

这个题目自我感觉说的不太明确, 知道算法可能还要注意一下两点才能AC:

(1) 从PBMC到问题站点, 只能在这个顺序上进行每个站点车辆数量的调整, 在从问题站点返回PBMC的时候不能调整路径上的站点, 所以这个就导致有可能从PBMC送出去车辆也有可能带回来车辆(直觉上好像不太合理, 既然要带回来, 那么从出去的时候干嘛不少送一点呢？但是没办法, 这个题目似乎就是这么要求的)

(2) 从哪些最短路径总选择调整的车辆的数量最小的那条时, 题目总的描述非常模糊以及容易误导， 题目中是这么说的：“If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.”， 我一开始理解成了只要比较送出去的车辆的数量就行了, 其实测试数据才不是这么测试的呢, 其实应该按照“首先选择send最少的，send相同时选择take back最少的。“这条标准从所有的最短路径中选择 (第七个case应该就是卡在这里).

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<string>
#define Max_len 510

using namespace std;

typedef struct node{
	int var;
	int len;
}node;

vector <node> map[Max_len];
int get, send, last_get, last_send, last_end;
int value, N, des, M, max_sum, min_time, end_len;
int last[Max_len], visited[Max_len], record[Max_len], temp[Max_len];
void dfs(int var, int time, int len);      //深搜得到所有的路径
int get_best(int len);   //得到最小的send和get

int main(){
	
	int flag, i, j, a, b, len;
	node temp;
	
	min_time = 100000;
    last_send = 1000000;
	scanf("%d %d %d %d", &value, &N, &des, &M);
	
	value /= 2;
	for(i = 1; i <= N; i++){
		scanf("%d", &record[i]);
	}

	for(i = 0; i < M; i++){
		scanf("%d %d %d", &a, &b, &len);
		temp.var = b; temp.len = len;
		map[a].push_back(temp);
		temp.var = a;
		map[b].push_back(temp);
	}

	visited[0] = 1;
	dfs(0, 0, 0);
	flag = 0;
	
	printf("%d", last_send);
	printf(" 0");
	for(i = 0; i < last_end; i++){
		printf("->%d", last[i]);
	}
	printf(" %d\n", last_get);
	return 0;
}

int get_best(int end_len){
	
	int i, temp_t;
	get = 0; send = 0;

	for(i = 0; i < end_len; i++){
		if(record[temp[i]] < value){
			temp_t = value - record[temp[i]];
			if(temp_t > get){
				temp_t -= get;
				get = 0;
				send += temp_t;
			}
			else{
				get -= temp_t;
			}
		}
		else{
			get += (record[temp[i]] - value);
		}
	}
        
	return send;
}

void dfs(int var, int time, int len){
	
	int i, j, size, vertex, hehe;
	
	if(var == des){
		if(time < min_time || (time == min_time && get_best(len) < last_send) || (time == min_time && get_best(len) == last_send && get < last_get)){
			get_best(len);
			min_time = time;
			last_send = send;
			last_end = len;
			last_get = get;
			for(j = 0; j < len; j++){
				last[j] = temp[j];
			}                     
		}
		return;
	}

	size = map[var].size();
	for(i = 0; i < size; i++){
		vertex = map[var][i].var;
		if(!visited[vertex]){
			visited[vertex] = 1;
			temp[len] = vertex;
			dfs(vertex, time + map[var][i].len, len + 1);
			visited[vertex] = 0;
		}
	}

}

pat 1018

原文：http://blog.csdn.net/huntinggo/article/details/18941253