先考虑无解的情况，为以下几种：\(dis_{i,j}+dis_{j,k}<dis_{i,k}\)，\(dis_{i,i}\neq 0\)，\(dis_{i,j}\neq dis_{j,i}\)，\(dis_{i,j}>K\)。先大力特判掉

然后来考虑没有边权为\(0\)的时候，把原图中所有的边分类，对于\((i,j)\)，如果存在\(k\)使得\(dis_{i,k}+dis_{k,j}=dis_{i,j}\)，那么称其为\(B\)类边，否则为\(A\)类边。显然\(A\)类边的权值就是\(dis_{i,j}\)，因为从其他地方走权值都大于自己。然后大力猜想一发对于所有\(B\)类边，权值可以取\([dis_{i,j},K]\)之间的数，接下来证明它

因为存在一条路径从\(i\)到\(j\)且权值为\(dis_{i,j}\)，那么这条路径\(F\)上的边数大于等于\(2\)，如果其上都是\(A\)类边，那么就算所有\(B\)取值为\(K\)也没关系。那么反证，假设其上有一条边为\(B\)类边，那么这条\(B\)类边也有对应一条与它权值相等的路径\(G\)。\(G\)不可能与\(F\)有任何一条边重复，否则我们可以在\(F\)上不走那条\(B\)边而是走\(G\)，那么少走了重复的那几条边，路径权值会变小，与\(F\)是最短路矛盾

综上，所有\(A\)类边取值固定，\(B\)类边可以取\([dis_{i,j},K]\)之间的边，判断一下边的类型，用乘法原理统计答案就好了

信心满满交上去结果只有\(30\)分，发现自己忘记考虑边权为\(0\)的情况了

如果有边权为\(0\)，那么我们可以把这两个点缩成一个点，而且不难发现最短路为\(0\)是具有传递性的，所以我们可以把互相之间最短路为\(0\)的点缩到一起，记其中点的个数为\(size_i\)，缩完点之后的图就是没有边权为\(0\)的情况了

考虑一个连通块内部，如果把\(0\)边当成实边，那么\(0\)边需要让所有的点联通，而其它的边的取值无所谓。记\(f_i\)为\(i\)个点的连通块中\(0\)边使所有点联通的方案数，那么有\[f_i=(K+1)^{C_{i}^2}-\sum_{j=1}^{i-1}K^{(i-j)\times j}(K+1)^{C_{i-j}^2}C_{i-1}^{j-1}f_j\]

上面的式子的意思就是，总共的方案减去不合法的方案，不合法的方案可以枚举与\(1\)同一个联通快的点的大小\(j\)，那么内部的方案就是\(f_j\)，然后\(j\)和\(i-j\)之间的边能为\(0\)，\(i-j\)内部随便连

上面是连通块的贡献，然后考虑边的贡献，设一条边连接的两个连通块大小分别为\(i,j\)，两个连通块之间的最短路长度为\(d\)，如果这条边是\(B\)类边，那么方案数就是\((K-d+1)^{i\times j}\)，如果是\(A\)类边，就是\((K-d+1)^{i\times j}-(K-d)^{i\times j}\)即合法的减去不合法的

然后就没有然后了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=505,P=998244353;inline int add(R int x,R int y){return x+y>=P?x=y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);    return res;}int a[N][N],vis[N][N],fa[N],f[N],fac[N],inv[N],sz[N];int n,K,res=1;inline int C(R int n,R int m){if(m>n)return 0;return mul(fac[n],mul(inv[m],inv[n-m]));}int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}bool ck(){    fp(i,1,n)if(a[i][i]!=0)return false;    fp(i,1,n)fp(j,i+1,n){        if(a[i][j]!=a[j][i])return false;        if(a[i][j]>K)return false;        fp(k,1,n)if(a[i][j]+a[j][k]