本文共 3061 字，大约阅读时间需要 10 分钟。

DIJ - 昂贵的聘礼 - POJ 1062

题意：

$首行输入等级限制m，以及物品数量n。$

$接着输入n组数据，每组包括非负整数P，L，X(X<n)，$

$分别代表每件物品的价格P，级别L，和该物品的补充物品的数量X。$

$接着输入X行数据，每行包括补充物品的编号I_i和优惠价格C_i。$

$优惠价格表示，可以通过先购买I_i号物品，则可以C_i的价格购得物品i。$

$现需要购买1号物品，可以通过购买一系列的补充物品来使得总花费减少。求最低花费是多少。$

Sample Input

1 410000 3 22 80003 50001000 2 14 2003000 2 14 20050 2 0

Sample Output

5250

数据范围：

$1\le N\le 100$

分析：

$设置虚拟源点0号点，0号点到其他点之间建立一条有向边，边权为直接购买该点所需的代价。$

$其他节点之间根据输入，建立有向边，边权为优惠价格。$

$样例如下图：$

$以0号点为源点跑一遍dijkstra即可。$

$另外，由于等级限制，中途购买到的所有商品的等级与1号商品的等级差不能超过m，$

$故我们需要枚举一个等级差的区间，在这个区间内跑最短路。$

$区间范围是：[level[1]-m+k,level[1]+k]，其中k\in [0,m]。$

$枚举m个区间，跑m遍最短路即可，记录下m遍最短路求出的最小的代价。$

代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=110,inf=0x3f3f3f3f;int n,m;int w[N][N],dis[N];int level[N];bool st[N];int dijkstra(int down,int up){       memset(dis,0x3f,sizeof dis);    memset(st,false,sizeof st);        dis[0]=0;    for(int i=1;i<=n+1;i++)    {           int t=-1;        for(int j=0;j<=n;j++)            if(!st[j] && (t==-1 || dis[t]>dis[j]))                t=j;                        st[t]=true;                for(int j=1;j<=n;j++)            if(down<=level[j]&&level[j]<=up)                dis[j]=min(dis[j],dis[t]+w[t][j]);    }        return dis[1];}int main(){       cin>>m>>n;        memset(w,0x3f,sizeof w);    for(int i=0;i<=n;i++) w[i][i]=0;        for(int i=1;i<=n;i++)    {           int price,cnt;        cin>>price>>level[i]>>cnt;        w[0][i]=min(w[0][i],price);        while(cnt--)        {               int id,cost;            cin>>id>>cost;            w[id][i]=min(w[id][i],cost);        }    }        int res=inf;    for(int i=level[1]-m;i<=level[1];i++) res=min(res,dijkstra(i,i+m));        cout<
       
        <
       
      
     
    
   

转载地址：http://etor.baihongyu.com/