[第一波模拟\day3\T3]{益智游戏}(game.cpp)

【问题描述】

小P和小R在玩一款益智游戏。游戏在一个正权有向图上进行。

小P控制的角色要从A点走最短路到B点，小R控制的角色要从C点走最短路到D点。

一个玩家每回合可以有两种选择，移动到一个相邻节点或者休息一回合。

假如在某一时刻，小P和小R在相同的节点上，那么可以得到一次特殊奖励，但是在每个节点上最多只能得到一次。

求最多能获得多少次特殊奖励。

【输入格式】

第一行两个整数n，m表示有向图的点数和边数。

接下来m行每行三个整数x_i，y_i，l_i，表示从x_i到y_i有一条长度为l_i的边。

最后一行四个整数A，B，C，D，描述小P的起终点，小R的起终点。

【输出格式】

输出一个整数表示最多能获得多少次特殊奖励。若小P不能到达B点或者小R不能到达D点则输出-1。

【样例输入输出】

game.in

game.out

5 5

1 2 1

2 3 2

3 4 4

5 2 3

5 3 5

1 3 5 4

【数据规模】

对于30%的数据，满足n≤50

对于60%的数据，满足n≤1000，m≤5000

对于100%的数据，满足n≤50000，m≤200000，1≤li≤500000000

【题解】

为了处理出最短路径涉及的块，跑4遍最短路，也就是在原图和反向图上跑最短路对AB和CD各做1次

之后标记两个最短路网的边，被标记两次的就是两个人能相遇的边

对这些被标记的边建一个新图，跑拓扑排序+Dp找DAG的最长路，最长路经即为解

#include <queue>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define oo 0x7fffffff - 1

#define max(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

inline int read()

	{

	int c = getchar(), x = 0;

	while(c < '0' || c > '9') c = getchar();

	while(c >= '0' &&  c <= '9') x = (x << 1) + (x << 3) + c - '0', c = getchar();

	return x;

	}

int ans, n, m, A, B, C, D, cnt, ncnt, fcnt, h[50003], nh[50003], fh[50003], d1[50003], d2[50003], hash[200003], du[50003], Q[50003], f[50003];

struct pt {int v, w, ne;} a[200003], na[200003], fa[200003];

struct ed {int u, v, w;} e[200003];

struct abcd {

	int fir, sec;

	bool operator < (const abcd oth) const {return sec > oth.sec;} };

priority_queue<abcd> q;

bool mark[50003];

inline void link(int u, int v, int w) {a[++cnt].v = v, a[cnt].w = w, a[cnt].ne = h[u], h[u] = cnt;}

inline void nlink(int u, int v, int w) {na[++ncnt].v = v, na[ncnt].w = w, na[ncnt].ne = nh[u], nh[u] = ncnt;}

inline void flink(int u, int v, int w) {fa[++fcnt].v = v, fa[fcnt].w = w, fa[fcnt].ne = fh[u], fh[u] = fcnt;}

void dijkstra(int x, int d[], pt a[], int h[])

	{

	for(int i = 1; i <= n; ++i) d[i] = oo, mark[i] = 0;

	d[x] = 0; q.push((abcd){x, 0});

	while(!q.empty())

		{

		int now = q.top().fir; q.pop();

		if(mark[now]) continue;

		mark[now] = 1;

		for(int j = h[now]; j; j = a[j].ne)

			if(!mark[a[j].v] && d[a[j].v] > d[now] + a[j].w)

				{

				d[a[j].v] = d[now] + a[j].w;

				q.push((abcd){a[j].v, d[a[j].v]});

				}

		}

	}

bool preced()

	{

	dijkstra(A, d1, a, h);

	dijkstra(B, d2, na, nh);

	if(d1[B] == oo || d2[A] == oo) return 0;

	for(int j = 1; j <= m; ++j) if(d1[e[j].u] + e[j].w + d2[e[j].v] == d1[B]) ++hash[j];

	dijkstra(C, d1, a, h);

	dijkstra(D, d2, na, nh);

	if(d1[D] == oo || d2[C] == oo) return 0;

	for(int j = 1; j <= m; ++j)

		{

		if(d1[e[j].u] + e[j].w + d2[e[j].v] == d1[D]) ++hash[j];

		if(hash[j] == 2) {flink(e[j].u, e[j].v, e[j].w); ++du[e[j].v];}

		}

	return 1;

	}

void sortdp()

	{

	for(int i = 1; i <= n; ++i) {f[i] = 1; if(!du[i]) Q[++Q[0]] = i;}

	for(int i = 1; i <= Q[0]; ++i)

		{

		int now = Q[i];

		for(int j = fh[now]; j; j = fa[j].ne)

			{

			f[fa[j].v] = max(f[fa[j].v], f[now] + 1);

			ans = max(ans, f[fa[j].v]);

			--du[fa[j].v];

			if(!du[fa[j].v]) Q[++Q[0]] = fa[j].v;

			}

		}

	printf("%d\n", ans);

	}

int main()

	{

	freopen("game.in", "r", stdin), freopen("game.out", "w", stdout);

	n = read(), m = read();

	for(int i = 1; i <= m; ++i)

		{

		e[i].u = read(), e[i].v = read(), e[i].w = read();

		link(e[i].u, e[i].v, e[i].w);

		nlink(e[i].v, e[i].u, e[i].w);

		}

	A = read(), B = read(), C = read(), D = read();

	if(preced()) sortdp();

	else puts("-1");

	fclose(stdin), fclose(stdout);

	return 0;

	}

巴特西