Solution
- 如果有人来看这篇题解，我就暂且认为大家都清楚题意了，这里不再赘述。
- 我们将给出的一段段时间的左节点向右节点之间连一条单向边，边权为奖金，然后因为可以有交叉的情况，我们可以将每一个节点向它前一个节点连一条边权为0的单向边。
- 然后跑最短路。
- 你会发现样例不过，然而思路没有问题，一个很关键的问题是他给的是时间段，也就是说样例中总区间0～4,有0～2和3～4是可以满足的，但是我们的做法中2到3没有边。
- 若考虑连上每一个节点与他下一个节点，明显会出错。
- 所以我们可以将给出的每个左右节点的右节点+1，然后再连边，最终取总区间左端点到总区间右端点+1的最短路即可。
（这种做法确实比线段树快）
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=86399+5,maxm=86399+5;
const ll Inf=0x3f3f3f3f3f3f3f3f;
ll dis[maxn];
int n,m,s,t,cnt,head[maxn];
bool vis[maxn];
struct Edge{int to,next;ll val;}e[maxm<<1];
void A(int x,int y,ll z){
e[++cnt].to=y;
e[cnt].next=head[x];
e[cnt].val=z;
head[x]=cnt;
}
void Dij(int S){
priority_queue<pair<ll,int> >q;
for(int i=s;i<=t+1;++i)dis[i]=Inf,vis[i]=0;
dis[S]=0;
q.push(make_pair(-dis[S],S));
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]&&dis[v]>dis[x]+e[i].val){
dis[v]=dis[x]+e[i].val;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main(){
scanf("%d%d%d",&n,&s,&t);
ll z;
for(int i=1,x,y;i<=n;++i){
scanf("%d%d%lld",&x,&y,&z);
A(x,y+1,z);
}
for(int i=t;i>s;--i)A(i,i-1,0LL);
Dij(s);
if(dis[t+1]!=Inf)printf("%lld
",dis[t+1]);
else printf("-1
");
return 0;
}