C++14(g++5.4) 解法, 执行用时: 90ms, 内存消耗: 14812K, 提交时间: 2020-05-17 15:00:49

#include <algorithm>
#include <array>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 2e5 + 5;
int N, M;
struct Edge {
  int to, w;
};
vector<Edge> E[MAXN];
array<int, MAXN> dis;
void spfa(int st);

int main() {
  //
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    E[y].push_back({x - 1, -1});
    E[x - 1].push_back({y, 1});
  }
  for (int i = 1; i <= N; i++) {
    E[i].push_back({i - 1, 0});
    E[i - 1].push_back({i, 1});
  }
  spfa(0);
  printf("%d\n", dis[N]);
  return 0;
}

array<bool, MAXN> vis;
void spfa(int st) {
  dis.fill(1e9);
  deque<int> Q;
  dis[st] = 0;
  Q.push_back(st);
  vis[st] = true;
  int cnt_circle = 0;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop_front();
    vis[u] = false;
    for (auto item : E[u]) {
      int v = item.to, w = item.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          if (++cnt_circle > 2e6) {
            dis[N] = -1;
            return;
          }
          if (!Q.empty() && dis[v] > dis[Q.front()])
            Q.push_back(v);
          else
            Q.push_front(v);
          vis[v] = true;
        }
      }
    }
  }
}

C++11(clang++ 3.9) 解法, 执行用时: 28ms, 内存消耗: 4180K, 提交时间: 2020-05-18 20:31:48

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 200010

int n,m,l[maxn],r[maxn];
int q[maxn],st=1,ed=1,f[maxn],ans=0;
void add(int x){while(st<=ed&&f[x]>f[q[ed]])ed--;q[++ed]=x;}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n+1;i++)l[i]=0,r[i]=i-1;
	for(int i=1,x,y;i<=m;i++)
	scanf("%d %d",&x,&y),l[y+1]=max(l[y+1],x),r[y]=min(r[y],x-1);
	for(int i=n;i>=1;i--)r[i]=min(r[i],r[i+1]);
	for(int i=2;i<=n+1;i++)l[i]=max(l[i],l[i-1]);
	int now=1;
	for(int i=1;i<=n+1;i++)
	{
		while(now<=r[i])
		{
			if(f[now]!=-1)add(now);
			now++;
		}
		while(st<=ed&&q[st]<l[i])st++;
		if(st<=ed)f[i]=f[q[st]]+1;
		else f[i]=-1;
	}
	printf("%d",max(f[n+1]-1,-1));
}