喵喵题。
考虑若所有点权都已确定，如何求 \(1\) 到 \(n\) 所有路径权值和的 \(\gcd\)。
考虑如何 check 一个 \(x\) 是否合法。\(x\) 合法的充要条件是，把不能从 \(1\) 到达的点和不能到达 \(n\) 的点扔掉后，存在一组 \(\{f_n\}\)，使得对于每条 \(u \to v\)，边权为 \(d\) 的边，都满足 \(f_v - f_u \equiv d \pmod x\)，且 \(f_1 = f_n = 0\)。\(f_i\) 的实际意义是，\(1 \to i\) 的所有路径的权值和模 \(x\) 的值。
但是这题不是边权而是点权。考虑拆点，在新图上连边 \(u \to u'\)，边权 \(a_u\)；\(u' \to u\)，边权 \(-a_u\)；原图 \(u \to v\) 的边在新图上连边 \(u' \longleftrightarrow v\)，边权 \(0\)。那么判是否存在一组 \(\{f_n\}\) 等价于新图的所有环权值和模 \(x\) 意义下都是 \(0\)。
新图若忽略边权实际上是一张无向图。所以跑出新图的一棵 dfs 树，设根到 \(i\) 的路径边权和为 \(g_i\)。若设一条非树边为 \(u \to v\)，边权为 \(d\)，那么需要满足 \(g_u - g_v + d \equiv 0 \pmod x\)。所以 \(x\) 是所有这样的 \(|g_u - g_v + d|\) 的因数。那么把所有 \(|g_u - g_v + d|\) 取 \(\gcd\) 就是答案。
还有个问题是点权可能不确定。点权不确定的点就不连 \(u\) 和 \(u'\) 之间的边。这样新图可能不连通，跑出一个 dfs 森林即可。
code
// Problem: E - GCD of Path Weights
// Contest: AtCoder - AtCoder Regular Contest 144
// URL: https://atcoder.jp/contests/arc144/tasks/arc144_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 600100;
ll n, m, a[maxn], ans, f[maxn], dep[maxn];
vector<int> G[maxn], rG[maxn];
vector<pii> T[maxn];
pii E[maxn];
bool vis1[maxn], vis2[maxn], vis[maxn];
void dfs1(int u) {
vis1[u] = 1;
for (int v : G[u]) {
if (!vis1[v]) {
dfs1(v);
}
}
}
void dfs2(int u) {
vis2[u] = 1;
for (int v : rG[u]) {
if (!vis2[v]) {
dfs2(v);
}
}
}
void dfs(int u) {
vis[u] = 1;
for (pii p : T[u]) {
ll v = p.fst, d = p.scd;
if (!vis[v]) {
f[v] = f[u] + d;
dep[v] = dep[u] + 1;
dfs(v);
} else if (dep[v] < dep[u]) {
ans = __gcd(ans, abs(f[u] - f[v] + d));
}
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
rG[v].pb(u);
E[i] = mkp(u, v);
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
dfs1(1);
dfs2(n);
for (int i = 1; i <= n; ++i) {
if (a[i] != -1 && vis1[i] && vis2[i]) {
T[i].pb(i + n, a[i]);
T[i + n].pb(i, -a[i]);
}
}
for (int i = 1; i <= m; ++i) {
int u = E[i].fst, v = E[i].scd;
if (vis1[u] && vis2[u] && vis1[v] && vis2[v]) {
T[u + n].pb(v, 0);
T[v].pb(u + n, 0);
}
}
T[1].pb(n + n, 0);
T[n + n].pb(1, 0);
for (int i = 1; i <= n * 2; ++i) {
int j = (i > n ? i - n : i);
if (!vis[i] && vis1[j] && vis2[j]) {
dfs(i);
}
}
printf("%lld\n", ans == 0 ? -1LL : ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}