[nowcoder 2020] 移动

一、题目

点此看题

二、解法

首先请明确两点：可以往回走！$dp$贪心死活想不出来的时候可以考虑下图论，思路要打开！

其实这道题如果用最短路的话就比较好想，我们的目的是让每个点向相邻的点转移（这样可以兼顾回退、等待、前进），但是我们要知道时间，怎么办？我们知道时间的目的是为了确定闸门的关闭，既然不能知道具体的时间，我们就通过闸门的关闭时间段来划分时间段，夹在两个之间的就当做一个可通行的状态，通过最短路可求出到达这个状态的最小时间，状态的编号就用夹住它的前面关闭时间段的编号，状态数是$O(n+m)$的。

建图怎么办？不难发现是边数$O(m)$的，因为只有相邻点之间的可通行时间段相交的时候才会产生边。但是如果你不注意建边的方式就很容易炸成部分分。一种很好的方法就是在$dj$的时候直接跑，由于访问的左端点是单增的（指的是我们到达这个状态的最小时间），那么如果一段区间和它不相交，那么以后都不相交，维护每个位置的指针即可。

#include <cstdio> #include <vector> #include <algorithm> #include <queue> using namespace std; const int M = 100005; const int inf = 0x3f3f3f3f; int read() { int num=0,flag=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int n,m,pos[M]; vector<int> dis[M]; struct range { int l,r; bool operator < (const range &b) const { return l<b.l; } };vector<range> v[M]; struct node { int x,id,l,r; bool operator < (const node &b) const { return l>b.l; } }; int dijk() { for(int i=0;i<=n+1;i++) { int len=v[i].size(); dis[i].resize(len); for(int j=0;j<len;j++) dis[i][j]=inf; v[i].push_back(range{inf,inf}); } priority_queue<node> q; q.push(node{0,0,0,inf-1}); dis[0][0]=0; while(!q.empty()) { node t=q.top();q.pop(); if(dis[t.x][t.id]<t.l) break; if(t.x==n+1) return t.l; int nl=t.l+1,nr=t.r+1; for(int p=t.x-1;p<=t.x+1;p+=2) { if(p<0) continue; while(v[p][pos[p]+1].l<=nl) pos[p]++; int len=v[p].size(); for(int i=pos[p];i+1<len;i++) { if(v[p][i].r>=nr) break; int cost=max(nl,v[p][i].r+1); if(cost<dis[p][i]) { dis[p][i]=cost; q.push(node{p,i,cost,v[p][i+1].l-1}); } } } } return 'n'+'m'+'s'+'l'; } signed main() { n=read();m=read(); for(int i=1;i<=m;i++) { int a=read(),b=read(),c=read(); v[a].push_back(range{b,c}); } for(int i=0;i<=n+1;i++) v[i].push_back(range{-1,-1}); for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end()); printf("%d\n",dijk()); }