【2018 NWERC D】Date Pickup 题解

题目大意

  有一幅 $n$ 个点 $m$ 条边的有向图，边有边权（代表通过所需时间），你在 $1$ 号点，女朋友在 $n$ 号点。
  你可以选择在 $1$ 号点延迟任意时间之后，选定一条路线开始游走，一旦开始游走就不能停下来。你的女朋友会在时间区间 $[a,b]$ 中的任意一个实数时间点 call 你，你一旦被 call 就要马上过去 $n$ 号点，女朋友的等待时间就是她 call 了之后到你到达所用的时间。
  求女朋友的最坏等待时间最小。

  $n,m \le 10^5,\ \ 0 \le a \le b \le 10^{12}$，边权 $\le 10^6$
  保证每个点至少有一条出边，即总是可以无限游走的。

  6s

题解

  官方题解有很多细节不是很懂，不过对我考场上的想法有很大的启发，于是完成了我考场上的想法。

  二分答案 $mid$。
  首先，如果到了 $[a,b]$ 这个时间段，我们必须随叫随到，因此我们可以知道这时候哪些点哪些边是能走的：对于点 $u$ 需满足 $dis(u,n) \le mid$，对于边 $(u,v,w)$ 需满足 $w+dis(v,n) \le mid$。这个时间段内我们只能在这个子图上走，除了开始的一点点（$a$ 时刻我们可能还在去这个子图的路上）。
  如果我们能从 $1$ 号点去到这个子图，那么接下来要做的事情就是：如果这个子图有环，我们就一直沿着环走，就合法了；如果这个子图没有环，它就是个 DAG，就可以在上面 dp 出一个最久逗留时间，让它 $\ge b$ 就好了。
  所以现在就是要判断从 $1$ 号点能不能到达这个子图，即会不会在 $a$ 时刻还没走到子图但是被 call 了然后去不了 $n$ 号点。
  假设在 $[a,b]$ 时间段我们最先到达的节点是 $x$，它的充要条件就是：1、$x$ 是子图上的点；2、$dis(1,x) \le a+mid-dis(x,n)$（即 $a$ 时刻 call 合法）。这样就相当于筛选出了子图的合法起点，可以做一个 bfs 筛去子图里起点不能到的点，然后做上面的拓扑找环和 dp。

  关于 DAG 上的 dp，初值是对于子图起点 $x$，$dp_x=a+mid-dis(x,n)$（即越晚出发越好，但要满足 $a$ 时刻 call 合法），然后按拓扑序求最长路径。

  注意一些特殊情况，比如 $1$ 号点本身是子图里的点的时候，只需判断 $dis(1,n) \le mid$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;
typedef pair<int,int> pr;

const int maxn=1e5+5;

int n,m;
LL a,b;
vector<pr> e[maxn],ef[maxn];

LL dis1[maxn],disn[maxn];
bool vis[maxn];
void dijkstra(int st,vector<pr> *e,LL *dis) {
	memset(dis,127,sizeof(LL)*(n+2));
	dis[st]=0;
	memset(vis,0,sizeof(vis));
	priority_queue<pair<LL,int>> Q;
	Q.push(make_pair(0,st));
	fo(i,1,n) {
		while (!Q.empty() && vis[Q.top().second]) Q.pop();
		if (Q.empty()) break;
		auto tp=Q.top(); Q.pop();
		vis[tp.second]=1;
		for(pr go:e[tp.second]) if (!vis[go.first] && dis[go.first]>-tp.first+go.second) {
			dis[go.first]=-tp.first+go.second;
			Q.push(make_pair(-dis[go.first],go.first));
		}
	}
}

bool valid[maxn],arrived[maxn];
vector<pr> et[maxn];
LL dp[maxn];
int dg[maxn];
void bfs(LL mid) {
	memset(dg,0,sizeof(dg));
	memset(arrived,0,sizeof(arrived));
	queue<int> Q;
	fo(i,1,n) {
		et[i].clear();
		if (valid[i] && dis1[i]<=a+mid-disn[i]) {
			Q.push(i);
			arrived[i]=1;
		}
	}
	while (!Q.empty()) {
		int cur=Q.front(); Q.pop();
		for(auto go:e[cur]) if (go.second+disn[go.first]<=mid) {
			if (!arrived[go.first]) Q.push(go.first), arrived[go.first]=1;
			et[cur].push_back(go);
			dg[go.first]++;
		}
	}
}
bool topo(LL mid) {
	memset(dp,0xbf,sizeof(dp));
	queue<int> Q;
	fo(i,1,n) if (arrived[i] && !dg[i]) Q.push(i);
	while (!Q.empty()) {
		int cur=Q.front(); Q.pop();
		if (dis1[cur]<=a+mid-disn[cur]) dp[cur]=max(dp[cur],a+mid-disn[cur]);
		if (dp[cur]>=b) return 1;
		for(auto go:et[cur]) {
			dp[go.first]=max(dp[go.first],dp[cur]+go.second);
			if (--dg[go.first]==0) Q.push(go.first);
		}
	}
	fo(i,1,n) if (arrived[i] && dg[i]) return 1;
	return 0;
}
bool check(LL mid) {
	fo(i,1,n) valid[i]=(disn[i]<=mid);
	if (valid[1]) return 1;
	bfs(mid);
	return topo(mid);
}

int main() {
	scanf("%lld %lld",&a,&b);
	scanf("%d %d",&n,&m);
	fo(i,1,m) {
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		e[x].push_back(make_pair(y,z));
		ef[y].push_back(make_pair(x,z));
	}
	
	dijkstra(1,e,dis1);
	dijkstra(n,ef,disn);
	
	LL l=0, r=dis1[n];
	while (l<=r) {
		LL mid=(l+r)>>1;
		if (check(mid)) r=mid-1; else l=mid+1;
	}
	
	printf("%lld\n",r+1);
}