poj2021

bfs

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define maxl 50
#define maxn 105

struct Elem
{
    int age;
    char name[maxl];
}decendant[maxn];

struct Edge
{
    int v, next, w;
}edge[maxn];

int n;
int head[maxn];
int ncount;
int dcount;
int q[maxn];
int ca;

bool operator < (const Elem &a, const Elem &b)
{
    if (a.age != b.age)
        return a.age > b.age;
    return strcmp(a.name, b.name) < 0;
}

int getid(char *name)
{
    for (int i = 0; i < dcount; i++)
        if (!strcmp(decendant[i].name, name))
            return i;
    strcpy(decendant[dcount].name, name);
    return dcount++;
}

void addedge(int a, int b, int w)
{
    edge[ncount].v = b;
    edge[ncount].w = w;
    edge[ncount].next = head[a];
    head[a] = ncount++;
}

void input()
{
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    strcpy(decendant[0].name, "Ted");
    decendant[0].age = 100;
    ncount = 0;
    dcount = 1;
    for (int i = 0; i < n; i++)
    {
        char name1[maxl];
        char name2[maxl];
        int w;
        scanf("%s%s%d", name1, name2, &w);
        int a = getid(name1);
        int b = getid(name2);
        addedge(a, b, w);
    }
}

void work()
{
    int front = 0, rear = 0;
    q[rear++] = 0;
    while (front != rear)
    {
        int u = q[front++];
        for (int i = head[u]; ~i; i = edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            decendant[v].age = decendant[u].age - w;
            q[rear++] = v;
        }
    }
}

void output()
{
    printf("DATASET %d\n", ca);
    for (int i = 1; i <= n; i++)
        printf("%s %d\n", decendant[i].name, decendant[i].age);
}

int main()
{
    //freopen("t.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    ca = 0;
    while (t--)
    {
        ca++;
        input();
        work();
        sort(decendant, decendant + n + 1);
        output();
    }
    return 0;
}