USACO 2008 March Gold Cow Jogging 解题报告

priority_queue<long, vector<long>, std::greater<long> >que;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct target
{
    int tar;
    long len;
};
struct node
{
    queue<target>to;
    priority_queue<long, vector<long>, std::greater<long> >ls;
};

node rcd[1005];
void dp(int pos, int k);
int main()
{
    int n, m, k, i, a;
    scanf("%d %d %d", &n, &m, &k);
    for(i = 0; i < m; i ++)
    {
        target tmp;
        scanf("%d %d %ld", &a, &tmp.tar, &tmp.len);
        rcd[a].to.push(tmp);
    }
    rcd[n].ls.push(0);
    for(i = n; i > 1; i --)
        dp(i, k);

    while(k --)
    {
        if(rcd[1].ls.size() > 0)
        {
            printf("%ld\n", rcd[1].ls.top());
            rcd[1].ls.pop();
        }
        else
            printf("-1\n");
    }
    return 0;
}

void dp(int pos, int k)
{
    queue<target> tmp;
    long tmpLen;
    target tmpTar;
    while(rcd[pos].ls.size() > 0 && k --)
    {
        tmp = rcd[pos].to;
        tmpLen = rcd[pos].ls.top();
        rcd[pos].ls.pop();
        while(tmp.size() > 0)
        {
            tmpTar = tmp.front();
            tmp.pop();
            rcd[tmpTar.tar].ls.push(tmpTar.len + tmpLen);
        }
    }
}