记录编号	27381	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov09] 找工作	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2011-09-19 20:57:59	内存使用	0.26 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>

using namespace std;

struct way_t {
    int en, p;
    way_t *next;
};

struct waylist {
    way_t *head;
};

int D, P, C, F, S;

waylist way[250];

void addway (waylist *l, const int en, const int p)
{
    way_t *newt = (way_t*)malloc(sizeof(way_t));
    newt->en = en;
    newt->p = p;
    newt->next = l->head;
    l->head = newt;
}

int spfa (const int S, const int limit)
{
    queue<int> q;
    q.push(S);

    int mw[C+1];
    bool boo[C+1];

    memset(mw, 0, sizeof(mw));
    memset(boo, 0, sizeof(mw));
    mw[S] = D;
    boo[S] = true;
    while (q.size())
    {
        int curr = q.front();
        q.pop();
        boo[curr] = false;

        for (way_t *p=way[curr].head; p; p=p->next)
            if (mw[curr]+p->p > mw[p->en])
            {
                if ((mw[p->en] = mw[curr] + p->p) > limit)
                    return -1;
                if (!boo[p->en])
                    q.push(p->en),
                    boo[p->en] = true;
            }
    }

    int max = 0;
    for (int i=1; i<=C; i++)
        if (mw[i] > max)
            max = mw[i];

    return max;
}

int main ()
{
    freopen("jobhunt.in", "r", stdin);
    freopen("jobhunt.out", "w", stdout);


    scanf("%d%d%d%d%d", &D, &P, &C, &F, &S);

    for (int i=0; i<P; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        addway(way+a, b, D);
    }

    for (int i=0; i<F; i++)
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        addway(way+a, b, D-p);
    }

    printf("%d\n", spfa(S, C*D));

    return 0;
}