#include <stdio.h>

struct Node;
struct Link
{
    unsigned int v;
    Node* nn;
};

struct Node
{
    unsigned int p;
    int l;
    unsigned int n;
    Link links[100];
};

int dl;
unsigned int min;

void dps(unsigned int now, Node *root, int minl, int maxl);

int main(int argc,char* argv[])
{
    unsigned int num, tmp, m, n;
    
    scanf("%d%d", &dl, &num);

    Node nodes[100];
    
    for(m=0; m<num; m++) {
        scanf("%d", &nodes[m].p);
        scanf("%d", &nodes[m].l);
        scanf("%d", &nodes[m].n);

        for(n=0; n<nodes[m].n; n++) {
            scanf("%d", &tmp);
            nodes[m].links[n].nn = &nodes[tmp-1];  
            scanf("%d", &(nodes[m].links[n].v));
        }
    }
    
    min = nodes[0].p;
    dps(0, nodes, nodes[0].l-dl, nodes[0].l+dl);
    printf("%d\n", min);

    return 0;
}

void dps(unsigned int now, Node *root, int minl, int maxl)
{
    int tminl = 0, tmaxl = 0;
    
    if(root->p + now < min) min = root->p + now;

    for(unsigned int n=0; n<root->n; n++) {
        if( minl <= root->links[n].nn->l && maxl >= root->links[n].nn->l)
        {   
            if(now + root->links[n].v > min) continue;

            tminl = root->links[n].nn->l - dl;
            tmaxl = root->links[n].nn->l + dl;
            tminl = tminl > minl ? tminl : minl;
            tmaxl = tmaxl > maxl ? maxl : tmaxl;
            if(tminl > tmaxl) continue;

            dps(now + root->links[n].v, root->links[n].nn, tminl, tmaxl);
        }
    }
}

• 汗，，dps，，Dota啊？ (1695) MrPan 2010-12-06 11:57:15
  • 额。。。错了。。。应该是DFS (0) Leon_Xu 2010-12-07 10:13:22