记录编号 |
294734 |
评测结果 |
AAAAAAAAAA |
题目名称 |
尼克的任务 |
最终得分 |
100 |
用户昵称 |
Hzoi_chairman |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.000 s |
提交时间 |
2016-08-12 17:36:11 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
using namespace std;
#define M(a,v) memset(a,v,sizeof(a))
const int maxn = 10010;
#define itn int
int n,m;
struct edge
{
int to,next,dis;
}a[maxn*4];
int len=0, head[maxn];
void insert(int x,int y,itn z){
a[++len].to=y; a[len].dis=z;
a[len].next=head[x]; head[x]=len;
}
int s[maxn],t[maxn],dis[maxn];
bool Comp(const int &a,const int &b){
if(a<b) return 1;
else return 0;
}
int Merge(int x){
int l=1,r=m+1;
while(l<=r){
int mid=(l+r)>>1;
if(t[x]<=s[mid]) r=mid-1;
else l=mid+1;
}
return l;
}
void Spfa(int x){
bool f[maxn]; M(f,0); f[x]=1;
deque<int> q; q.push_back(x);
M(dis,63); dis[x]=0;
while(!q.empty()){
int k=q.front(); q.pop_front(); f[k]=0;
for(int i=head[k];i;i=a[i].next){
int p=a[i].to;
if(dis[p]>dis[k]+a[i].dis){
dis[p]=dis[k]+a[i].dis;
if(!f[p]){
f[p]=1;
if(!q.empty() && dis[p]<dis[q.front()]) q.push_front(p);
else q.push_back(p);
}
}
}
}
printf("%d\n",n-dis[n]);
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
insert(x-1,x+y-1,y);
s[i]=x-1; t[i]=x+y-1;
}
sort(s+1,s+1+m,Comp);
s[m+1]=n;
for(int i=1;i<=m;i++){
int temp=Merge(i);
//printf("End=%d s=%d\n",t[i],s[temp]);
if(s[temp]!=t[i]){
insert(t[i],s[temp],0);
}
}
if(s[1]!=0) insert(0,s[1],0);
Spfa(0);
}
int Main(){
freopen("lignja.in","r",stdin);
freopen("lignja.out","w",stdout);
init(); return 0;
}
int ZHOUYOUERZI=Main();
int main(){;}