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;
}