POJ1062【单源最短路】
原题描述：
[url=http://acm.pku.edu.cn/JudgeOnline/problem?id=1062]见原题[/url]
题目大意：
探险家想获得某样物品，可以直接买，花费P；也可以获得另外一种物品（递归调用。。。），再加上V金币来换取。
另外，与探险家交换的人都有个级别。他只能在一个长度为M + 1的下界不定的范围的级别的人内交换。举个例子，M为1，他要是与级别为3的人交换了，就不能与级别为1的人交换了，反之亦然。
求出，探险家想获取物品0所需花费的最少金币数。
解题思路：
我的想法是，在可以互换的物品间建立一条边，度为其需要的额外金币V。这样便建起了一个图。以0为起始点，用dijkstra算法求出它到每个点的最短 路。这个最短路便是，用该物品经过多次换算，得到物品0所需的最少的金币数。再加上买这个物品的费用，便是获得物品0所需的最小金币数了。
另外，这里还有一个问题，就是每个人都级别的问题了。我是通过两个数组，分别保存换取到物品i时的最大的级别和最小的级别。于是，在dijkstra比较时，加入级别的判定。这样，便能轻松的解决这个问题。
代码:
#include <stdio.h>
#define MAXN 101
#define inf 1000000000
typedef int elem_t;
int Lev[101];
int Lev_lowest[101],Lev_max[101];
int M,N;
void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre){
int v[MAXN],i,j,k;
for (i=0;i<n;i++)
min=inf,v=0,pre=-1;
for (min[s]=0,j=0;j<n;j++){
for (k=-1,i=0;i<n;i++){
if (!v&&(k==-1||min<min[k])){
k=i;
}
}
for (v[k]=1,i=0;i<n;i++){
if (!v&&min[k]+mat[k]<min && (Lev <= M + Lev_lowest[k]) && Lev >= Lev_max[k] - M){
min=min[k]+mat[pre=k];
Lev_lowest = Lev_lowest < Lev_lowest[k]?Lev_lowestev_lowest[k];
Lev_max = Lev_max > Lev_max[k]?Lev_maxev_max[k];
}
}
}
}
int map_wedding[101][101];
int _abs(int x){
if(x >= 0){
return x;
}
return -x;
}
int main(){
while(scanf("%d %d",&M,&N) != EOF){
int i,k,z;
for(i = 0; i <= N; ++i){
for(k = 0; k <= N; ++k){
map_wedding[k] = inf;
}
}
int P[101],X;
int max_l = -1;
for(i = 0; i < N; ++i){
scanf("%d %d %d",&,&Lev,&X);
Lev_lowest = Lev_max = Lev;
for(k = 0; k < X; ++k){
int T,V;
scanf("%d %d",&T,&V);
T--;
map_wedding[T] = V;
}
}
for(i = 0; i < N; ++i){
for(k = i; k < N; ++k){
if(map_wedding[k] != inf){
if(_abs(Lev - Lev[k]) > M){
map_wedding[k] = map_wedding[k] = inf;
}
}
}
}
//for(i = 0; i < N; ++i){
// for(k = 0; k < N; ++k){
// printf("%d\t",map_wedding[k]);
// }
// printf("\n");
//}
int min[101],pre[101];
dijkstra(N,map_wedding,0,min,pre);
int min_cost = P[0];
for(i = 1; i < N; ++i){
// printf("%d %d\t",min,pre);
min_cost = min_cost > min + P?min + P:min_cost;
}
//printf("\n");
printf("%d\n",min_cost);
}
return 0;
}
测试数据
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
1 4
10000 2 1
2 4000
6000 3 1
3 2000
3000 2 1
4 1000
1000 1 0
结果
5250
9000
以上代码未经过优化。