C20220711T4 移动

牛牛从0出发走到 \(n+1\) ，每秒可以选择向前走一步，向后走一步或者不走，有一些时刻不让呆在某一格，求最短到达时间， \(n\leq 10^5\) 。

这是一道很神奇的压轴题（其实并没有什么高深的算法）。把不让呆在某一个转换成可以呆在某一格，用 \((x,i,t)\) 表示一个状态：在第 \(x\) 的位置走到第 \(i\) 个可以走到的点的时间 \(t\) 。并用 \(f[i]\) 表示到第 \(i\) 段时间的最短时间，然后用优先队列不断更新状态，最后就可以得到答案。

#include<bits/stdc++.h>
#define ll long long
#define rg register
#define FOR(x,y,z) for(rg int x=y;x<=z;++x)
#define ROF(x,y,z) for(rg int x=y;x>=z;--x)
#define mp std::make_pair
#define pb push_back
#define pii std::pair< int , int >
#define Inf 0x3f3f3f3f
namespace IO{
	inline ll in(){
		ll x=0,f=1;
		char c;
		do{
			c=getchar();
			if(c=='-')
				f=-1;
		}while(c<'0' || c>'9');
		while(c<='9' && c>='0'){
			x=(x<<3)+(x<<1)+c-'0';
			c=getchar();
		}
		return f*x;
	}
}
using namespace IO;

std::vector< pii > v[200005],cur;
struct node{
	int id,x,t;
	node(int a,int b,int c){
		id=a;
		x=b;
		t=c;
	}
};

int n,m;
int id[200005],f[200005];
bool operator > (node a,node b){
	return a.t>b.t;
}

std::priority_queue< node , std::vector<node> , std::greater<node> > q;

void calc(node p,int x){
	int r=v[p.x][p.id-id[p.x]].second;
	int i=std::lower_bound(v[x].begin(),v[x].end(),mp(p.t+1,0))-v[x].begin()-1;
	if(v[x][i].second>=p.t+1){
		if(f[id[x]+i]>p.t+1){
			f[id[x]+i]=p.t+1;
			q.push(node(id[x]+i,x,p.t+1));
		}
	}
	++i;
	while(i<(int)v[x].size() && v[x][i].first<=r+1){
		if(f[id[x]+i]>v[x][i].first){
			f[id[x]+i]=v[x][i].first;
			q.push(node(id[x]+i,x,v[x][i].first));
		}
		++i;
	}
}

void solve(){
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	q.push(node(0,0,0));
	while(q.size()){
		node p=q.top();
		q.pop();
		if(p.t>f[p.id])
			continue;
		if(p.x>0)
			calc(p,p.x-1);
		if(p.x<n+1)
			calc(p,p.x+1);
	}
}

int main(){
	n=in(),m=in();
	FOR(i,1,m){
		int a=in(),b=in(),c=in();
		v[a].pb(mp(b,c));
	}
	v[0].pb(mp(0,Inf));
	v[n+1].pb(mp(0,Inf));
	id[1]=1;
	FOR(i,1,n){
		std::sort(v[i].begin(),v[i].end());
		cur.clear();
		int r=-1;
		FOR(j,0,(int)v[i].size()-1){
			pii p=v[i][j];
			if(p.first>r+1)
				cur.pb(mp(r+1,p.first-1));
			r=std::max(r,p.second);
		}
		cur.pb(mp(r+1,Inf));
		v[i]=cur;
		id[i+1]=id[i]+v[i].size();
	}
	solve();
	printf("%d\n",f[id[n+1]]);
	return 0;
}