poj 1062 昂贵的聘礼

Description

Input

Output

Sample Input

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

Sample Output

5250

最短路变形：优惠看做边权，物品最初价格为以此为终点的附加花费。求第一个顶点到每个顶点的最短路的最小值。

#include"stdio.h"
#include"string.h"
#define N 110
#define min(a,b) (a<b?a:b)
int g[N][N],p[N],l[N],mark[N];
int n;
const int inf=0x7fffffff;
int dijkstra()
{
    int i,index,mm;
    int dis[N];
    for(i=1;i<=n;i++)
        dis[i]=p[i];
    while(1)
    {
        mm=inf;
        index=-1;
        for(i=1;i<=n;i++)
        {
            if(!mark[i]&&mm>dis[i])
            {
                mm=dis[i];index=i;
            }
        }
        if(index==-1)
            break;
        mark[index]=1;
        for(i=1;i<=n;i++)
        {                 //g[index][i]>=0代表当前边存在
            if(!mark[i]&&g[index][i]>=0&&dis[i]>dis[index]+g[index][i])
                dis[i]=dis[index]+g[index][i];
        }
    }
    return dis[1];
}
int main()
{
    int m,x,y,i,j,v;
    while(scanf("%d%d",&m,&n)!=-1)
    {
        memset(g,-1,sizeof(g));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&p[i],&l[i],&x);
            while(x--)
            {
                scanf("%d%d",&y,&v);
                g[y][i]=v;          //单向边
            }
        }
        int ans=inf;
        for(i=1;i<=n;i++)           //枚举每一个顶点
        {
            for(j=1;j<=n;j++)       
            {
                if(l[i]<l[j]||l[i]-l[j]>m)
                    mark[j]=1;          //当前顶点作为最高等级
                else
                    mark[j]=0;
            }
            int t=dijkstra();
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj 1062 昂贵的聘礼,布布扣,bubuko.com

poj 1062 昂贵的聘礼

原文：http://blog.csdn.net/u011721440/article/details/26673825