传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=313
试题描述：
WZJ的公司放假了！为了保证假期期间公司的安全，WZJ决定雇佣一些人来看守公司。有M个大学生来应聘，他们想要的工资是Ci元，可以为WZJ从第Si天到Ti天看守公司。WZJ是个决定在花钱前提下雇佣一些人，使得从第1天到第N天都至少有一个人看守公司，你能帮帮他吗(若无解输出"No Answer.")？
输入：
第一行为两个正整数N，M。
第二行至第M+1行第i+1行为3个正整数Si、Ti、Ci。
输出：
输出WZJ最少花的钱数(若无解输出"No Answer.")。
输入示例：
5 4
1 2 3
2 4 1
4 5 2
1 5 8
输出示例：
6
其他说明：
1<=N,M<=100000
1<=Si<=Ti<=N
1<=Ci<=2000
线段树练习题
题解：先想到将每一天抽象成点，来一个（L,R）的人就添一条边L->R+1权值为工资，然后跑一遍最短路貌似就搞定了
---------当然没搞定了啊，比如你让(1,6),(4,8)情何以堪啊，所以先搞一下所有的(i,i-1)权值为0的边就好了.
当然了，此题本来就是要用线段树瞎搞一个背包动规……
最短路：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=+,INF=-1u>>;
struct Tedge{int x,y,w,next;}adj[maxn*];int fch[maxn],ms=;
void AddEdge(int u,int v,int w){
adj[++ms]=(Tedge){u,v,w,fch[u]};fch[u]=ms;return;
}
bool vis[maxn];int dist[maxn],n,m;
void SPFA(){
queue<int>Q;memset(vis,false,sizeof(vis));
for(int i=;i<=n+;i++)dist[i]=INF;dist[]=;
Q.push();vis[]=true;
while(!Q.empty()){
int u=Q.front();Q.pop();vis[u]=false;
for(int i=fch[u];i;i=adj[i].next){
int v=adj[i].y;
if(dist[v]>dist[u]+adj[i].w){
dist[v]=dist[u]+adj[i].w;
if(!vis[v]) vis[v]=true,Q.push(v);
}
}
} return ;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){
n=read();m=read();int a,b,c;
for(int i=n+;i>;i--) AddEdge(i,i-,);
for(int i=;i<=m;i++){
a=read();b=read();c=read();
AddEdge(a,b+,c);//printf("-AddEdge-%d %d %d\n",k,j,c);
} return;
}
void work(){
SPFA();
//for(int i=1;i<=ms;i++)printf("-Edge- %d to %d is %d\n",adj[i].x,adj[i].y,adj[i].w);
//for(int i=1;i<=n+1;i++) printf("dist[%d]=%d\n",i,dist[i]);
return;
}
void print(){
if(dist[n+]>=INF) puts("No Answer.");
else write(dist[n+]),putchar('\n');
return;
}
int main(){
init();work();print();return ;
}
/*
5 3
1 2 3
1 1 5
3 5 6
*/
线段树：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const int INF=;
int first[maxn],next[maxn],s[maxn],v[maxn],f[maxn];
int minv[maxn*],ql,qr,x,val;
void update(int o,int L,int R)
{
if(L==R) minv[o]=val;
else
{
int M=L+R>>,lc=o<<,rc=lc|;
if(x<=M) update(lc,L,M);
else update(rc,M+,R);
minv[o]=min(minv[lc],minv[rc]);
}
}
int query(int o,int L,int R)
{
if(ql<=L&&R<=qr) return minv[o];
int M=L+R>>,ans=INF,lc=o<<,rc=lc|;
if(ql<=M) ans=min(ans,query(lc,L,M));
if(qr>M) ans=min(ans,query(rc,M+,R));
return ans;
}
int main()
{
int n,m,a,b,c;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
s[i]=a; v[i]=c;
next[i]=first[b];
first[b]=i;
}
for(int i=;i<=n*;i++) minv[i]=INF;
update(,,n);
for(int i=;i<=n;i++)
{
f[i]=INF;
for(int j=first[i];j;j=next[j])
{
ql=s[j]-;qr=i-;
f[i]=min(f[i],v[j]+query(,,n));
}
x=i; val=f[i];
if(val!=INF) update(,,n);
}
if(f[n]==INF) puts("No Answer.");
else printf("%d\n",f[n]);
return ;
}