POJ 1062 昂贵的聘礼

非常老的题目了，枚举层次dijkstra，G++AC

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

Source

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=1200;

int dist[maxn],g[maxn][maxn],N,M;
int level[maxn],within[maxn],value[maxn];
bool vis[maxn];

int dijkstra()
{
    for(int i=1;i<=N;i++)
        dist[i]=(i==1)?0:INF;
    memset(vis,0,sizeof(vis));

    for(int i=1;i<=N;i++)
    {
        int mark=-1,mindis=INF;
        for(int j=1;j<=N;j++)
        {
            if(!vis[j]&&dist[j]<mindis&&within[j])
            {
                mindis=dist[j];
                mark=j;
            }
        }
        vis[mark]=1;

        for(int j=1;j<=N;j++)
        {
            if(within[j]&&!vis[j])
            {
                dist[j]=min(dist[j],dist[mark]+g[mark][j]);
            }
        }
    }

    int ans=INF;
    for(int i=1;i<=N;i++)
    {
        ans=min(dist[i]+value[i],ans);
    }

    return ans;
}

int main()
{
    while(scanf("%d%d",&M,&N)!=EOF)
    {
        memset(g,63,sizeof(g));
        for(int i=1;i<=N;i++)
        {
            int t;
            scanf("%d%d%d",&value[i],&level[i],&t);

            while(t--)
            {
                int to,bb;
                scanf("%d%d",&to,&bb);
                g[i][to]=bb;
            }
        }

        int min_cost=INF;
        int kinglevel=level[1];

        for(int i=0;i<=M;i++)
        {
            memset(within,0,sizeof(within));
            for(int j=1;j<=N;j++)
            {
                if(level[j]>=kinglevel-M+i&&level[j]<=kinglevel+i)
                    within[j]=1;
            }
            min_cost=min(min_cost,dijkstra());
        }

        printf("%d\n",min_cost);
    }
    return 0;
}

POJ 1062 昂贵的聘礼

原文：http://blog.csdn.net/u012797220/article/details/18503631