本文主要是介绍POJ1062 Expensive dowry 【最短路dijkstra】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
详细看：http://blog.csdn.net/lyy289065406/article/details/6645852
简单说一下:每个物品是一个结点，边的权值是，edge[u][v]的值表示用物品u换物品v的价格
一开始所有物品都置为原价，即所有dist[i]为原价，用dijkstra算法，算出0点（啥物品都没有）到各点的最短距离，求出dist[1]即为花费
枚举每个物品的等级为这条交易链的最高等级，把所有等级高于它的或者比它小超过等级限制的点都剔除，可以用bool数组剔除，然后用上述的dijkstra
注意一个问题：
最好一开始dist全置为最大值int_max,然后你把所有点赋值原价格也好，仅仅把可行点（满足上述权值条件的点）赋原价格也好，如果点1被剔除了则continue也好，不continue也好，都对。反之，则有可能错，比如，你一开始把所有dist都置为0（或者所有可行点置为原价（此时点1有可能已经被剔除而你没有continue，进入了dijkstra算法中）），dist[1]还是0，结果return dist[1]，就WA了。
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int SIZE=11111;
int level,n;
int price[SIZE];
int lev[SIZE];
int x[SIZE];
int g[SIZE][SIZE];
int dist[SIZE];
bool visit[SIZE];
void init_input()
{int u,v;cin>>level>>n;for(int i=1;i<=n;i++){cin>>price[i]>>lev[i]>>x[i];for(int j=1;j<=x[i];j++){cin>>u>>v;g[u][i]=v;}}
}
int dijkstra(int v0)
{for(int i=1;i<=n;i++){dist[i]=price[i];}for(int i=1;i<=n;i++){int node=0;int min=(1<<31)-1;for(int ii=1;ii<=n;ii++){if(!visit[ii]&&dist[ii]<min){min=dist[ii];node=ii;}}if(node==0)break;visit[node]=true;for(int ii=1;ii<=n;ii++){if(!visit[ii]&&g[node][ii]>0&&dist[ii]>dist[node]+g[node][ii]){dist[ii]=dist[node]+g[node][ii];}}}return dist[1];
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifinit_input();int mxlevel;int minans=(1<<31)-1;int tmpans;for(int i=1;i<=n;i++){mxlevel=lev[i];for(int ii=1;ii<=n;ii++){if(lev[ii]>mxlevel||mxlevel-lev[ii]>level)visit[ii]=true;elsevisit[ii]=false;}tmpans=dijkstra(i);//cout<<tmpans<<endl;minans=min(minans,tmpans);}cout<<minans<<'\n';
}
这篇关于POJ1062 Expensive dowry 【最短路dijkstra】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
