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 200000int graph[MAX][MAX];/* graph[0][i]表示物品i的原始价格,graph[v][w]表示优惠价格 */int rank[MAX];intn;intprice[MAX];/* price[v]买物品v的最低价格 */charfinal[MAX];/* 顶点是否加入了集合, 加入了集合就意味着该顶点从图中排除掉 */int dijkstra(){inti, 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(){intlimit;inti, j, m;intadj, 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-7for (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;}