记录编号	206013	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]清理牛棚	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.536 s
提交时间	2015-11-05 21:24:58	内存使用	1.72 MiB

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 87000L;

int n,m,e,f[MAXN];

bool vis[MAXN];

struct Edge {
	int v,w;
};

vector <Edge> G[MAXN];

void spfa() {
	queue<int> q;
	f[m] = 0;q.push(m);vis[m] = 1;
	while(!q.empty()) {
		int u = q.front();q.pop();vis[u] = 0;
		for(int i = 0,r = G[u].size();i < r;++ i) {
			int v = G[u][i].v;
			if(f[v] > f[u] + G[u][i].w) {
				f[v] = f[u] + G[u][i].w;
				if(!vis[v]) {
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
}

int main(){
	freopen("clean.in","r",stdin);
	freopen("clean.out","w",stdout);
	scanf("%d%d%d",&n,&m,&e);
	for(int i = 1,l,r,w;i <= n;++ i) {
		scanf("%d%d%d",&l,&r,&w);
		G[l].push_back((Edge){r + 1,w});
	}
	for(int i = e + 1;i >= m; i --) {
		f[i] = 0x3f3f3f3f;
		G[i].push_back((Edge){i - 1,0});
	}
	spfa();
	printf("%d",f[e + 1] == 0x3f3f3f3f ? -1 : f[e + 1]);
	return 0;
}