本文主要是介绍poj 1062 dij，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=1062
这一题不难发现，就是一个最短路径的问题，题目已经规定最终要换到的物品是第一个，然后给出另外几个可以优惠的节点，比如这个图，0-1的最小代价是0-4-3-1 也就是5250。
如何建图？0是源点，map【0】【i】代表第i个物品直接兑换的价值，map[j][i]代表如果已经有了编号j的物品，从j物品再map[j][i]的价值就可以兑换到i。
注意题目说 “如果两人地位等级差距超过了M，就不能"间接交易"。“
枚举N个物品主人的等级作为商人的等级，商人只能和比他小，并且差距《=M的人交易。
#include<cstdio>
#include<cstring>
#define MAXN 105
#define inf 0x0fffffff
struct good
{
int price,level,replace;
}g[MAXN];
int map[MAXN][MAXN];
bool vis[MAXN];
int dist[MAXN];
int M,N;
int dij()
{
int i,j;
for(i=0;i<=N;i++)
dist[i]=map[0][i];
for(i=1;i<=N;i++)
{
int min=inf,minid=0;
for(j=1;j<=N;j++)
{
if(!vis[j]&&dist[j]<min)
{
min=dist[j];
minid=j;
}
}
vis[minid]=true;
for(j=1;j<=N;j++)
if(!vis[j]&&dist[j]>dist[minid]+map[minid][j])
dist[j]=dist[minid]+map[minid][j];
}
return dist[1];
}
int main()
{
//freopen("C:\\1.txt","r",stdin);
scanf("%d%d",&M,&N);
int i,j;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
map[i][j]=inf;
for(i=1;i<=N;i++)
{
scanf("%d%d%d",&g[i].price,&g[i].level,&g[i].replace);
map[0][i]=g[i].price;
for(j=1;j<=g[i].replace;j++)
{
int u,w;
scanf("%d%d",&u,&w);
map[u][i]=w;
}
}
int min=inf;
int allow_level=0;
for(i=1;i<=N;i++)
{
allow_level=g[i].level;
for(j=1;j<=N;j++)
if(g[j].level>allow_level||allow_level-g[j].level>M)
vis[j]=true;
else
vis[j]=false;
int temp=dij();
if(min>temp)
min=temp;
}
printf("%d\n",min);
return 0;
}
这篇关于poj 1062 dij的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
