长乐集训 - NOI模拟赛（三十五）「订正未完成」

$\text{score：0 + 0 + 0 = 0 rk：32/39}$

Problem A：最短路

题面

题解

该路径一定是从 $1$ 走到 $n$ 后，在从 $n$ 返回 $1$ 时在外围走一遭，再回到 $1\to n$ 的路径走一段，再出去向 $1$ 走一段。。

设往外围走时的起点为 $a$ 类点，回到 $1\to n$ 路径的点为 $b$ 类点，容易知道 $a$ 和 $b$ 交错出现才可能最优，那么整个图大概就这么个样（起点和终点不作标记）

令 $f_{i,j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，为 $a$ 类点，倒数第二个点为 $j$，为 $b$ 类点

令 $g_{i,j}$ 表示从 $1$ 走到 $i$，最后一个点为 $i$，$i,j$ 都为 $b$ 类点

实际上 $f$ 可以直接转移，不需要 $g$，但这样复杂度时 $O(n^4)$ 的，故 $g$ 相当于辅助函数

用类似 $Dijkstra$ 的形式转移，设 $i$ 到 $j$ 的最短路径为 $d_{i,j}$（即使路径上所有点的权值和最小，包括 $i,j$）

假设此时取出 $f_{x,y}$ 则有
$$g_{k,y}=min\{f_{x,y}+d_{x,k}-p_x\}$$
即多出一个 $a$ 类点 $x$ 到 $b$ 类点 $k$ 的路径

假设此时取出 $g_{x,y}$，则有
$$f_{k,x}=min\{g_{x,y}+d_{x,k}+d_{k,y}-p_x-p_y-p_k\}$$
直接用堆维护是 $O(n^3\log n)$ 的，但观察一下发现在 $j$ 相同时，每次可以枚举取最小值，故最终复杂度 $O(n^3)$

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 250 + 10;

const int INF = 0x3f3f3f3f;

int N, M;
int a[MAXN]= {0}, d[MAXN][MAXN]= {0};

int f[MAXN][MAXN], g[MAXN][MAXN];
bool visit[2][MAXN][MAXN]= {false};
struct node {
	int val, x, y;
	node (int val = 0, int x = 0, int y = 0) : val (val), x (x), y (y) {}
} ;
node maxf[MAXN], maxg[MAXN];
void getm (node& a, node b) { if (b.val < a.val) a = b; }
void workf (int j) {
	maxf[j] = node (INF, 0, 0);
	for (int i = 1; i <= N; i ++)
		if (! visit[0][i][j])
			getm (maxf[j], node (f[i][j], i, j));
}
void workg (int j) {
	maxg[j] = node (INF, 0, 0);
	for (int i = 1; i <= N; i ++)
		if (! visit[1][i][j])
			getm (maxg[j], node (g[i][j], i, j));
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	memset (d, INF, sizeof (d));
	memset (f, INF, sizeof (f));
	memset (g, INF, sizeof (g));
	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++) { a[i] = getnum (); d[i][i] = a[i]; }
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum ();
		d[u][v] = a[u] + a[v];
	}
	for (int k = 1; k <= N; k ++)
		for (int i = 1; i <= N; i ++)
			for (int j = 1; j <= N; j ++)
				d[i][j] = min (d[i][j], d[i][k] + d[k][j] - a[k]);
	if (d[1][N] >= INF || d[N][1] >= INF) { puts ("-1"); return 0; }
	f[1][1] = a[1]; for (int i = 1; i <= N; i ++) workf (i), workg (i);
	while (true) {
		node mf, mg; mf = mg = node (INF, 0, 0);
		for (int i = 1; i <= N; i ++) getm (mf, maxf[i]), getm (mg, maxg[i]);
		int type = mf.val <= mg.val ? 0 : 1;
		getm (mf, mg);
		if (mf.val >= INF) break;
		int x = mf.x, y = mf.y;
		if (type) {
			visit[1][x][y] = true;
			for (int k = 1; k <= N; k ++)
				if (k != y)
					f[k][x] = min (f[k][x], g[x][y] + d[x][k] + d[k][y] - a[x] - a[y] - a[k]);
			workf (x), workg (y);
		}
		else {
			visit[0][x][y] = true;
			for (int k = 1; k <= N; k ++)
				g[k][y] = min (g[k][y], f[x][y] + d[x][k] - a[x]);
			workf (y), workg (y);
		}
	}
	cout << f[N][N] << endl;

	return 0;
}