poj1062

中文题，不翻译不解释。

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAX=120;
int M,N,X,T,V;
int map[MAX][MAX];
int topo[MAX];
int visted[MAX];
typedef struct NODE
{
    int level;
    int price;
}NODE;
NODE nodes[MAX];
int num=0;
void Dfs(int v)
{
    visted[v]=1;
    for (int i=1;i<=N;i++)
    {
        if (!visted[i] && map[v][i]>0)//unvisited
        {
            Dfs(i);
        }
    }
    topo[num++]=v;
}
void MinCost()
{
    int i,j;
    for (i=0;i<N;i++)
    {
        for (j=i+1;j<N;j++)
        {
            if (map[topo[j]][topo[i]]>0)
            {
                int temp=nodes[topo[i]].price+map[topo[j]][topo[i]];
                if ((temp<nodes[topo[j]].price))
                {
                    nodes[topo[j]].price=temp;
                }
            }
        }
    }
    printf("%d\n",nodes[1].price);
}
int main()
{
    int i,j;
    memset(map,0,sizeof(map));
    memset(visted,0,sizeof(visted));
    scanf("%d%d",&M,&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d%d%d",&nodes[i].price,&nodes[i].level,&X);
        for (j=1;j<=X;j++)
        {
            scanf("%d%d",&T,&V);
            map[i][T]=V;
        }
        if( abs(nodes[i].level-nodes[1].level) > M )
        {
            for(j=1;j<N;j++)
            {
                map[j][i]=-1;
            }
        }
    } 
    Dfs(1);
    MinCost();
    return 0;
}

poj1062

原文：http://blog.csdn.net/zhengnanlee/article/details/18348387