我是个懒惰的人。中午开题想了一会没思路，于是大胆猜想，然后想了一种和正解没半毛钱关系的思路。

首先，完全图的最短距离是 $1$，想让最短距离从 $1$ 变成 $2$ 只需要删除一条边。

但是，从 $2$ 以后最短距离每增加 $1$ 就至少删 $n$ 条边起步。

所以直接猜想：$1$ 到 $n$ 的最短距离不超过 $\frac{\inf}{n}$。这里 $\inf$ 是个特定阙值，我取到了 $6 \times 10^5$。

然后就好办了，直接暴力 dp 就行，长度大于这个阙值直接输出 $-1$ 即可，一旦 dp[n] 有值就输出。

但是会有一个问题：本题需要取模，万一答案是 $P$ 就不会跳出循环，拿到 99 分。

所以我把模数变成了 $P \times 100$，最后取模即可。

最近感觉自己好容易想出玄学思路啊，估计是玄学题做多了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,inf=6e5,P1=998244353,P=P1*100;
int dp[N],dp1[N];vector<int>G[N];
signed main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dp[1]=1;int sum=1,res=0;
	while(!dp[n])
	{
		for(int i=1;i<=n;i++)dp1[i]=sum;sum=0;
		for(int i=1;i<=n;i++)for(int j:G[i])dp1[i]=((dp1[i]-dp[j])%P+P)%P;
		for(int i=1;i<=n;i++)dp[i]=dp1[i],sum=(sum+dp[i])%P;
		res++;if(res>inf/n){cout<<-1;return 0;}
	}
	cout<<dp[n]%P1;
	return 0;
}

题目传送门

题目大意

给你一张 $n$ 个点的完全图和 $m$ 条边，让你求出该完全图删除这 $m$ 条边后最短路径条数。

思路

考虑对于每个点，按照与 $1$ 的距离分层，相同距离的在同一层，样例 $1$ 的图如下：

其中 $1$ 在第 $1$ 层，$2,4$ 在第 $2$ 层，$3,5$ 在第 $3$ 层，$6$ 在第 $4$ 层。

接下来考虑如何求出每个点和 $1$ 号点的距离。

我们考虑 bfs，记 set 维护当前未被访问的点，取出队首后，枚举补图中所有与它有连边的点，如果他们在集合中，则将他们标记，遍历完后，没有被标记的点就是可以转移到的下一层的点。

然后考虑如何统计方案数。

显然，$f_{v \in to_u}=\sum f_u$，其中满足 $dis[v]=dis[u]+1$。考虑如何在正确的时间复杂度内求得它。注意到删除的边只有 $m$ 条，可以考虑总的贡献减去删除的边的贡献。具体实现方法就是先把所有的 $f_v$ 赋值成 上一层的点的 $f$ 值之和。然后对于上一层的点连出去的所有需要删除的边，如果终点在这一层中，则减去这个 $f_x$。最后输出 $f_n$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200200,mod=998244353;
inline int read();
int n,m,sum;
set<int>G[N];
set<int>p[N];
int f[N];
int dis[N];
set<int>S,S1;
queue<int>q;
signed main(){
	n=read(),m=read();
	for(int i=2;i<=n;i++)
		S.insert(i);
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		G[u].insert(v);
		G[v].insert(u);
	}
	q.push(1);
	dis[1]=1;
	while(q.size()){
		S1=S;
		int u=q.front();q.pop();
		for(int x:G[u]){
			if(S1.find(x)!=S1.end())
				S1.erase(x);
		}
		for(int v:S1){
			dis[v]=dis[u]+1;
			q.push(v);
			S.erase(v);
		}
	}
	if(!dis[n]){
		puts("-1");
		return 0;
	}
	f[1]=sum=1;
	for(int i=1;i<=n;i++)
		p[dis[i]].insert(i);
	for(int i=2;i<=dis[n];i++){
		for(int x:p[i])
			f[x]=sum;
		for(int x:p[i-1]){
			for(int y:G[x]){
				if(p[i].find(y)!=p[i].end())
					(f[y]+=mod-f[x])%=mod;
			}
		}
		sum=0;
		for(int x:p[i])
			(sum+=f[x])%=mod;
	}
	printf("%lld\n",f[n]);
	return 0;
}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,M=998244353;
int n,m,t[N],f[N],vs[N];
vector<int> v[N];
signed main(){
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	queue<int>q;
	q.push(1);
	int d=1,ct=0,sm=0;f[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vs[x]=1;ct++;sm=(sm+f[x])%M;
		for(int i:v[x]){
			if(vs[i])continue;
			t[i]++;f[i]=(f[i]-f[x]+M)%M;
		}
		if(q.empty()){
			for(int i=1;i<=n;i++){
				if(vs[i])continue;
				if(t[i]<ct){
					q.push(i);
					vs[i]=1;
					f[i]=(f[i]+sm)%M;
				}
				else f[i]=t[i]=0;
			}	
			d++;ct=sm=0;
		} 
	}
	if(vs[n]==0)cout<<-1;
	else cout<<f[n]%M;
}