本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：http://uoj.ac/problem/279
算法一：
$n<=4$时直接上暴力就可以了，爆搜30分；
算法二：
对于没有$d(i,j)(i!=j)=0$的情况，考虑如果不存在$d(i,k)+d(k,j)=d(i,j)$的情况，则只能让$i$，$j$这条边$=d(i,j)$；否则，$(i,j)$这条边的权值就必须$>=d(i,j)$。所以对于每条边，如果满足上式，则方案数乘上$(k-d[i][j]+1)$即可。结合算法一，期望得分60分；
算法三：
我们考虑$d[i][j]$可以等于$0$的情况，首先我们把所有距离为$0$的点缩成一个团，因为他们之间距离为$0$，对于外界而言他们是完全等价的，不妨看成一个整体;
当我只考虑团与团之间的时候转化成了算法二的情况，但是计算有所不同，因为团与团之间可能有大量重边，所以我需要分类讨论，如果存在“中转点”，那么方案数就是所有重边的各自权值取值个数的乘积，否则重边中至少有一条需要等于最短路径，其余的随意，这个可以用容斥计算。
再考虑团内部的情况，我可以这样想，设$f[i]$为$i$个点的集合之间的使得两两最短距离为$0$的方案数，$g[i]$为$i$个点构成的图的所有方案的方案数。那么单独考虑集合中某个点$p$，则容易想到，如果把两两最短距离为$0$的集合称为一个连通块，那么$p$所在的连通块的$size$如果$<i$则说明不合法，即$size<i$都不合法。那么我们得到了一种经典的容斥方法：用所有的构图方案-$p$所在的连通块的$size<i$的情况。我们可以枚举这个$size$，当$size=j$时，显然我们需要选取另外从$i-1$个点中选$j-1$个点（$p$已经默认选好了），再考虑$p$所在的连通块的方案数就是$f[j]$，而$p$之外的情况就是$g[i-j]$，最后考虑$p$所在连通块与外界相连的情况，就是需要保证相连的边均为正整数，否则就不满足假设了，即$K^{(n-i)*i}$种方案数，这些都乘起来。以上的所有方案用乘法原理乘起来就可以了。
推导式：
${g[n]=(K+1)^{frac{n*(n-1)}{2}}}$
${f[n]=g[n]-sum_{i=1}^{n-1} f[i]*g[n-i]* K^{i*(n-i)}*C_{n-1}^{i-1}}$
不懂的可以看看我的算法三代码，有详细注释。
算法一+算法二：60分：
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 411;
const int MOD = 998244353;
int n,k,dis[MAXN][MAXN];
int w[MAXN][MAXN],cnt,f[MAXN][MAXN];
int dui[MAXN*MAXN][2];
LL ans;
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline bool check(){
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=w[i][j];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=k)
for(int j=1;j<=n;j++)
if(i!=j && k!=j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(f[i][j]!=dis[i][j]) return false;
return true;
}
inline void dfs(int x){
if(x==cnt+1) { if(check()) ans++; return ; }
int from=dui[x][0],to=dui[x][1];
for(int i=0;i<=k;i++) { w[from][to]=w[to][from]=i; dfs(x+1); }
}
inline void work(){
n=getint(); k=getint();
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=getint();
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dui[++cnt][0]=i,dui[cnt][1]=j;
if(n<=4) { dfs(1);}
else {
bool flag; ans=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) {
//if(i==j) continue;
flag=false;
for(int l=1;l<=n;l++) {
if(l==i || l==j) continue;
if(dis[i][l]+dis[l][j]==dis[i][j]) { flag=true; break; }
}
if(flag)
ans*=(LL)(k-dis[i][j]+1),ans%=MOD;
}
}
printf("%lld",ans);
}
int main()
{
work();
return 0;
}
算法三：100分：
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 411;
const int MOD = 998244353;
int n,K,dis[MAXN][MAXN],D[MAXN][MAXN];
int belong[MAXN],cnt,size[MAXN];
LL ans,f[MAXN],g[MAXN],C[MAXN][MAXN];
//f[i]表示为内部距离为0的团的内部连边方案数,g[i]表示任意一个大小为n的图的连边方案数
inline void No_solution(){ printf("0"); exit(0); }
inline LL fast_pow(LL x,LL y){ LL r=1; while(y>0) { if(y&1) r*=x,r%=MOD; x*=x; x%=MOD; y>>=1;} return r; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void check_false(){//考虑不合法的情况
//不对称
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(dis[i][j]!=dis[j][i])
No_solution();
//还可以松弛
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=k)
for(int j=1;j<=n;j++)
if(j!=i && j!=k && dis[i][j]>dis[i][k]+dis[k][j]) No_solution();
}
inline void work(){
n=getint(); K=getint(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { dis[i][j]=getint(); if(dis[i][j]>K) No_solution(); }
check_false(); ans=1; bool flag; LL now;
//将距离为0缩成团
for(int i=1;i<=n;i++) {
if(dis[i][i]) No_solution(); if(belong[i]) continue;
belong[i]=++cnt; size[cnt]++;
for(int j=i+1;j<=n;j++) if(dis[i][j]==0) belong[j]=cnt,size[cnt]++;
}
//缩团之后跑算法一
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(belong[i]!=belong[j]) D[belong[i]][belong[j]]=dis[i][j];
for(int i=1;i<=cnt;i++) {
for(int j=i+1;j<=cnt;j++) {
flag=false;//按照算法一计算每条边的贡献
for(int k=1;k<=cnt;k++) {
if(k==i || k==j) continue;
if(D[i][k]+D[k][j]==D[i][j]) flag=true;
}
//两个团之间有size[i]*size[j]条边，分两种情况讨论
//存在中转点的话，则中间的所有边都要大于等于D[i][j]
if(flag) ans*=fast_pow(K-D[i][j]+1,size[i]*size[j]),ans%=MOD;
//否则，中间的边就是一条等于，其余的全都大于等于，用容斥可以算出来至少一条的情况
else ans*=fast_pow(K-D[i][j]+1,size[i]*size[j])-fast_pow(K-D[i][j],size[i]*size[j]),ans%=MOD;
}
}
C[0][0]=1; for(int i=1;i<=400;i++) { C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j],C[i][j]%=MOD; }
//计算团的内部的贡献，可预处理所有情况
for(int i=1;i<=n;i++) g[i]=fast_pow(K+1,i*(i-1)/2);
for(int i=1;i<=n;i++) {
f[i]=g[i]; now=0;
for(int j=1;j<i;j++) {
now=C[i-1][j-1];
now*=fast_pow(K,j*(i-j)); now%=MOD;
now*=f[j]; now%=MOD;
now*=g[i-j]; now%=MOD;
f[i]-=now; f[i]%=MOD;
}
f[i]+=MOD; f[i]%=MOD;
}
for(int i=1;i<=cnt;i++) ans*=f[size[i]],ans%=MOD;
ans+=MOD; ans%=MOD;
printf("%lld",ans);
}
int main()
{
work();
return 0;
}