考虑整个图是一个点双怎么做。
显然如果有重边并且两条边边权一样就寄了。否则我们可以把它们当成一条边。
考虑一个二度点 \(u\) 和与它相连的边 \((v, u), (u, w)\)。我们可以把它缩成边 \((v, w)\)。如果新边已经存在并且边权不等于这两条边边权就寄了。缩点可能会产生一些新的二度点，用队列维护。
剩下的点除了 \(1, n\) 是度数 \(\ge 3\) 的点。可以证明如果最后有度数 \(\ge 3\) 的点就一定不行。因为可以得出一条边的边权为 \(0\)，与题设矛盾。
考虑整个图不是点双。考虑添加边 \((1, n, \text{dis}(1, n))\)。只保留和 \(1, n\) 在同一个点双的点即可。因为不在就不能从 \(1\) 到这个点再到 \(n\)。
然后就转化成了整个图是一个点双，用上面的做法即可。
时间复杂度 \(O((n + m) \log n)\)。
code
#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 = 200100;
ll n, m, deg[maxn];
vector<pii> G[maxn];
set<pii> T[maxn];
struct node {
ll u, d;
node(ll a = 0, ll b = 0) : u(a), d(b) {}
};
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
ll f[maxn];
bool vis[maxn];
int dfn[maxn], low[maxn], tim, cnt, stk[maxn], top;
vector<int> S[maxn];
void dfs(int u, int fa) {
dfn[u] = low[u] = ++tim;
stk[++top] = u;
for (pii p : G[u]) {
ll v = p.fst;
if (v == fa) {
continue;
}
if (!dfn[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
++cnt;
while (1) {
int x = stk[top--];
S[cnt].pb(x);
if (x == v) {
break;
}
}
S[cnt].pb(u);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
}
void solve() {
scanf("%lld%lld", &n, &m);
while (m--) {
ll u, v, d;
scanf("%lld%lld%lld", &u, &v, &d);
G[u].pb(v, d);
G[v].pb(u, d);
}
priority_queue<node> pq;
mems(f, 0x3f);
f[1] = 0;
pq.emplace(1, 0);
while (pq.size()) {
int u = pq.top().u;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (f[v] > f[u] + d) {
f[v] = f[u] + d;
if (!vis[v]) {
pq.emplace(v, f[v]);
}
}
}
}
G[1].pb(n, f[n]);
G[n].pb(1, f[n]);
dfs(1, -1);
mems(vis, 0);
for (int i = 1; i <= cnt; ++i) {
bool f1 = 0, f2 = 0;
for (int u : S[i]) {
f1 |= (u == 1);
f2 |= (u == n);
}
if (f1 && f2) {
for (int u : S[i]) {
vis[u] = 1;
}
}
}
for (int u = 1; u <= n; ++u) {
if (!vis[u]) {
continue;
}
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (vis[v]) {
auto it = T[u].lower_bound(mkp(v, -1));
if (it != T[u].end() && it->fst == v && it->scd != d) {
puts("1");
return;
}
T[u].emplace(v, d);
}
}
deg[u] = (int)T[u].size();
}
queue<int> q;
int cnt = 0;
for (int i = 2; i < n; ++i) {
cnt += vis[i];
if (deg[i] == 2) {
q.push(i);
}
}
while (q.size()) {
--cnt;
int u = q.front();
q.pop();
pii p1 = *T[u].begin(), p2 = *(--T[u].end());
ll v1 = p1.fst, d1 = p1.scd, v2 = p2.fst, d2 = p2.scd;
T[v1].erase(mkp(u, d1));
T[v2].erase(mkp(u, d2));
auto it = T[v1].lower_bound(mkp(v2, -1));
if (it != T[v1].end() && it->fst == v2) {
if (it->scd != d1 + d2) {
puts("1");
return;
}
T[v2].erase(mkp(v1, it->scd));
T[v1].erase(it);
T[v1].emplace(v2, d1 + d2);
T[v2].emplace(v1, d1 + d2);
if ((--deg[v1]) == 2 && v1 != 1 && v1 != n) {
q.push(v1);
}
if ((--deg[v2]) == 2 && v2 != 1 && v2 != n) {
q.push(v2);
}
} else {
T[v1].emplace(v2, d1 + d2);
T[v2].emplace(v1, d1 + d2);
}
}
puts(cnt ? "1" : "0");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}