P8426 题解

题目大意

给一张 $n$ 个点 $m$ 条边的带权无向连通图，问是否存在一条 $1\to n$ 的简单路径长度与最短路长度不同。

数据范围：$n\le 10^5,m\le 2\times 10^5$。

思路分析

首先我们考虑简单一点的情况：不妨设整张图点双联通，感觉上这张图不能太复杂，否则肯定会找到解。

手模样例可以发现：假如这张图同胚于 $K_4$，即有四个点之间能找到六条边不交的路径将它们两两连接，那么这个图一定无解：

不妨设这四个点是 $a,b,c,d$，假设这张图依然无解，简单推理一下：

• 由于 $w(a\to b\to c)=w(a\to d\to b\to c)$，因此 $w(a,d)+w(d,b)=w(a,b)$。
• 由于 $w(a\to d\to c)=w(a\to b\to d\to c)$，因此 $w(a,d)=w(a,b)+w(b,d)$。

因此 $w(b,d)=w(a,b)-w(a,d)=w(a,d)-w(a,b)=0$，又因权值都是正整数，因此假设不成立，这样的图必然有解。

因此我们得到：同胚于 $K_4$ 的点双联通图必定有解。

注意到不同胚于 $K_4$ 的点就是广义串并联图，考虑广义串并联图方法简化这张图：

• 删一度点：直接删除，不影响答案。
• 叠合重边：如果两条边权一样无事发生，否则产生一条边权为 $-\infty$ 的边。
• 缩二度点：产生一条权值为两边权之和的新边。

注意增广的过程中要保证 $1,n$ 两个点不能入队，最后假如的图里只剩一条 $1\to n$ 的边，且边权不为 $-\infty$ 则合法，否则显然一定不合法。

然后考虑如何把图变成点双联通的，首先如果 $1,n$ 点双联通，直接缩点，取出 $1,n$ 所在的点双联通分量作为原图即可。

若 $1,n$ 不点双联通，那么连接一条 $1,n$ 之间的边，权值为他们之间的最短路长度，显然不影响答案判定，且能使得 $1,n$ 点双联通。

时间复杂度 $\mathcal O(m\log m)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
int n,m;
struct Edge { int v; ll w; };
vector <Edge> G[MAXN];
ll dis[MAXN];
bool vis[MAXN];
inline ll Dijk() {
	memset(dis,0x3f,sizeof(dis));
	priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> Q;
	Q.push({dis[1]=0,1});
	while(Q.size()) {
		int u=Q.top()[1]; Q.pop();
		if(vis[u]) continue; vis[u]=true;
		for(auto e:G[u]) if(dis[e.v]>dis[u]+e.w) Q.push({dis[e.v]=dis[u]+e.w,e.v});
	}
	return dis[n];
}
vector <int> vdcc;
int dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp;
inline void tarjan(int u) {
	dfn[u]=low[u]=++dcnt,stk[++tp]=u;
	for(auto e:G[u]) {
		int v=e.v;
		if(!dfn[v]) {
			tarjan(v),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				int k; vector <int> cur{u};
				do k=stk[tp--],cur.push_back(k); while(k!=v);
				sort(cur.begin(),cur.end());
				if(cur.front()==1&&cur.back()==n) vdcc=cur;
			}
		} else low[u]=min(low[u],dfn[v]);
	}
}
bool inq[MAXN];
map <int,ll> g[MAXN];
inline void link(int u,int v,ll w) {
	if(g[u].count(v)) {
		if(w!=g[u][v]) g[u][v]=g[v][u]=-1;
	} else g[u][v]=g[v][u]=w;
}
queue <int> Q;
inline void upd(int x) { if(x!=1&&x!=n&&g[x].size()<=2) Q.push(x); }
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;++i) {
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	ll dist=Dijk();
	G[1].push_back({n,dist});
	G[n].push_back({1,dist});
	tarjan(1);
	for(int i:vdcc) inq[i]=true;
	for(int u:vdcc) for(auto e:G[u]) if(inq[e.v]) link(u,e.v,e.w);
	for(int i:vdcc) upd(i);
	while(Q.size()) {
		int u=Q.front(); Q.pop();
		for(auto e:g[u]) g[e.first].erase(u);
		if(g[u].size()==2) {
			int x=g[u].begin()->first,y=g[u].rbegin()->first;
			ll c=g[u].begin()->second,d=g[u].rbegin()->second;
			link(x,y,(~c&&~d)?c+d:-1);
		}
		for(auto e:g[u]) upd(e.first);
		g[u].clear();
	}
	if(g[1].count(n)&&~g[1][n]&&g[1].size()==1) puts("0");
	else puts("1");
	return 0;
}