题意是如果把floyd算法的k循环写在了最内层，有多少dis[i][j]还是正确的。n是顶点数，m是单向边数，n<=2000,m<=5000。
dis[i][j]是i到j的最短路长度，w[i][j]是i到j的边权。
注意到m只有5000，图不是很稠密，可以做n次Dijkstra得到dis数组，这部分复杂度是O(nmlogm)。
1.如果dis[i][j]==w[i][j],那么按照题意中的算法仍然能得到正确的结果。此时记can[i][j]=1。
2.如果存在x，使得can[i][x]==1&&can[x][j]==1&&x在i到j的任意一条最短路上，那么can[i][j]=1。
答案就是can[i][j]=1的有序组（i,j）数量。
直接这么算can[i][j]复杂度太高，我们注意到can[i][*]和can[*][j]的运算本质上是集合求交，可以利用bitset维护。
同时，枚举i,则i到j的所有最短路经过的点集pot[j]也可以通过bitset维护，具体做法是每次枚举一个i,就重新把顶点按照到i的最短路长度排序，从小到大计算pot[j]。如果dis[i][j]+w[j][k]==dis[i][k],则pot[k]|=pot[j]（到k的最短路一定是由到k相邻的点的最短路计算而来，所以这样算出来的pot[k]不会遗漏）。
这样总复杂度应该是O(nmlogm+n2m/32),只能说勉强冲得过去，手写bitset应该快一些，但我懒了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+11;
const int M=5e3+11;
int n,m,top=-1,nowi;
struct edge
{
int to;
ll val;
edge* nest;
}e[M<<1],*v[N];
ll dis[N][N],w[N][N];
struct ob
{
int num;
ll dist;
};
bool operator <(const struct ob &p,const struct ob &q){return p.dist>q.dist;}
priority_queue <ob> pq;
void addedge(int from,int to,int val)
{
e[++top].to=to;
e[top].val=val;
e[top].nest=v[from];
v[from]=&e[top];
}
bitset <N> f[N],g[N],pot[N];
int ord[N],ans;
int cmp(int p,int q)
{
if(dis[nowi][p]==-1) return 0;
else if (dis[nowi][q]==-1) return 1;
else return dis[nowi][p]<dis[nowi][q];
}
void Dijkstra(int now)
{
int i;
struct ob cur;
edge* ne;
for(i=1;i<=n;i++) dis[now][i]=1e18;
pq.push((ob){now,0});
while(!pq.empty())
{
cur=pq.top();
pq.pop();
if(dis[now][cur.num]!=1e18) continue;
dis[now][cur.num]=cur.dist;
for(ne=v[cur.num];ne;ne=ne->nest)if(dis[now][ne->to]==1e18)pq.push((ob){ne->to,cur.dist+ne->val});
}
}
int main()
{
int i,j,k,from,to;
ll val;
edge* ne;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) w[i][j]=1e18;
for(i=1;i<=m;i++)
{
scanf("%d%d%lld",&from,&to,&val);
w[from][to]=val;
addedge(from,to,val);
}
for(i=1;i<=n;i++) Dijkstra(i);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(w[i][j]==dis[i][j]) f[i][j]=g[j][i]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) ord[j]=j;
nowi=i;
sort(ord+1,ord+n+1,cmp);
for(j=1;j<=n;j++) pot[j].reset(),pot[j][j]=1;
for(j=1;j<=n;j++)for(ne=v[ord[j]];ne;ne=ne->nest)if(dis[i][ord[j]]+ne->val==dis[i][ne->to]) pot[ne->to]|=pot[ord[j]];
for(j=1;j<=n;j++)if((f[i]&g[j]&pot[j]).count())f[i][j]=g[j][i]=1;
}
for(i=1;i<=n;i++) ans+=f[i].count();
printf("%d\n",ans);
return 0;
}