poj 1062 dijkstra算法求最优价格

 

#include <stdio.h>
#include <string.h>

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define MAX 101

#define MAX_INT 200000

int 	graph[MAX][MAX];	/* graph[0][i]表示物品i的原始价格,graph[v][w]表示优惠价格 */
int 	rank[MAX];
int		n;

int		price[MAX];			/* price[v]买物品v的最低价格 */
char	final[MAX];			/* 顶点是否加入了集合, 加入了集合就意味着该顶点从图中排除掉 */

int dijkstra()
{
	int		i, v, w, min;

	//开始时,各个物品的最优价格就是原始价格
	for (v = 1; v <= n; v++) {
		price[v] = graph[0][v];
	}

	for (i = 1; i <= n; i++) {
		debug("未加入集合的点及其花费 = ");
		for (w = 1; w <= n; w++) {
			if (!final[w]) {
				debug("%d:%d ", w, price[w]);
			}
		}
		debug("\n");
		min = MAX_INT;
		v = 0;
		//从未加入集合的顶点中选择花费最小的物品
		for (w = 1; w <= n; w++) {
			if (!final[w]) {
				if (price[w] < min)  {
					min = price[w];
					v = w;
				}
			}
		}
		if (v == 0) break;
		debug("顶点%d的花费最小,加入集合, price[%d] = %d\n", v, v, price[v]);
		final[v] = 1;
		//找到v的所有邻接点
		for (w = 1; w <= n; w++) {
			if (!final[w] && graph[w][v] > 0 && (price[v]+graph[w][v]) < price[w]) {
				price[w] = price[v] + graph[w][v];
				debug("更新顶点%d的最小花费为%d\n", w, price[w]);
			}
		}	
	}
	return price[1];
}

int main()
{
	int		limit;
	int		i, j, m;
	int		adj, cost, min_cost;

	scanf("%d %d", &limit, &n);

	//建图
	for (i = 1; i <= n; i++) {
		scanf("%d %d %d", &graph[0][i], rank+i, &m);
		while (m--) {
			scanf("%d", &adj);
			scanf("%d", &graph[i][adj]);
		}
	}
	//打印图
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			debug("%d ", graph[i][j]);
		}
		debug("\n");
	}

	min_cost = MAX_INT;
	//枚举等级范围, 比如酋长的等级为5, 等级限制为2, 
	//那么每个人允许的等级为(3,4,5,6,7), 一条最优路线出现的等级范围可以是3-5, 4-6, 5-7
	for (i = rank[1]-limit; i <= rank[1]; i++) {
		//对于范围(i, i+limit), 确定哪些顶点可以用
		debug("对于范围(%d,%d)允许的顶点为\n", i, i+limit);
		for (j = 1; j <= n; j++) {
			if (rank[j] < i || rank[j] > i+limit) {		/* 不在范围内的点排除掉 */
				final[j] = 1;
			}
			else {
				final[j] = 0;
				debug("%d ", j);
			}

		}
		debug("\n");
		cost = dijkstra();
		debug("范围(%d,%d)的花费为%d\n", i, i+limit, cost);
		if (cost < min_cost) {
			min_cost = cost;
		}
	}
	printf("%d\n", min_cost);
	return 0;
}