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