记录编号	205847	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]清理牛棚	最终得分	100
用户昵称	waynest	是否通过	通过
代码语言	C++	运行时间	0.500 s
提交时间	2015-11-05 19:20:22	内存使用	1.54 MiB

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct node
{
    int to,v;
};
vector <node> map[86404];
queue <int> q;
bool in[86404];
int n,m,e;
int data1,data2,data3;
int f[86404];
 
void spfa()
{
    f[m]=0;
    q.push(m);
    in[m]=true;
    int now,tmp;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        in[now]=false;
        for(int i=0;i<map[now].size();++i)
        {
            tmp=map[now][i].to;
            if(f[tmp] > f[now] + map[now][i].v)
            {
                f[tmp] = f[now] + map[now][i].v;
                if(!in[tmp])
                {
                    q.push(tmp);
                    in[tmp] = true;
                }
            }
        }
    }
}
 
int main()
{
    freopen("clean.in","r",stdin);
    freopen("clean.out","w",stdout);
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&data1,&data2,&data3);
        map[data1].push_back( (node) {data2+1,data3} );
    }
    for(int i=e+1;i>=m;--i)
    {
        map[i].push_back( (node) {i-1,0} );
        f[i]=0x3fffffff;
    }
    spfa();
    if(f[e+1] == 0x3fffffff) printf("-1");
    else printf("%d",f[e+1]);
    return 0;
 
 
}