| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
线段树优化DP,AC留念,留下源码#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;
const int oo = 0x3f3f3f3f;
int N, S, T;
struct Node {
int from, to, cost;
} nodes[10000];
int dp[86400];
bool comp(Node a, Node b) {
if(a.from == b.from) {
return a.to < b.to;
}
return a.from < b.from;
}
int ST[86400 << 2];
void Push_Up(int rt) {
ST[rt] = min(ST[lson], ST[rson]);
}
void Update(int L, int R, int k, int l, int r, int rt) {
if(l == r) {
ST[rt] = k;
return;
}
int m = (l + r) >> 1;
if(L <= m) {
Update(L, R, k, l, m, lson);
}
if(m < R) {
Update(L, R, k, m + 1, r, rson);
}
Push_Up(rt);
}
int Query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return ST[rt];
}
int m = (l + r) >> 1;
int MI = oo;
if(L <= m) {
MI = min(MI, Query(L, R, l, m, lson));
}
if(m < R) {
MI = min(MI, Query(L, R, m + 1, r, rson));
}
return MI;
}
int main() {
scanf("%d %d %d", &N, &S, &T);
T ++;
for(int i = 0; i < N; i ++) {
scanf("%d %d %d", &nodes[i].from, &nodes[i].to, &nodes[i].cost);
nodes[i].to ++;
}
sort(nodes, nodes + N, comp);
memset(dp, oo, sizeof(dp));
memset(ST, oo, sizeof(ST));
dp[S] = 0;
Update(S, S, 0, 0, T, 1);
for(int i = 0; i < N; i ++) {
int pre_cost = Query(nodes[i].from, nodes[i].to, 0, T, 1);
if(dp[nodes[i].to] > pre_cost + nodes[i].cost) {
dp[nodes[i].to] = pre_cost + nodes[i].cost;
Update(nodes[i].to, nodes[i].to, dp[nodes[i].to], 0, T, 1);
}
}
if(dp[T] == oo) {
printf("-1\n");
} else {
printf("%d\n", dp[T]);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator