最短路
求最短路经过的所有路径，一般点不多，都可以暴力所有区间，check是不是最短路的一部分
注意 这里的cnt是最后一层的，而不是所有的
#include <bits/stdc++.h>
using namespace std ;typedef long long ll ;
const int inf = 0x3f3f3f3f ;
const int maxn = 550 ;
int edge[maxn][maxn] ;
int dis[maxn][maxn] ;
int cnt[maxn][maxn] ;
void floyd(int n ){for(int i = 1 ; i <= n ; i ++ ) dis[i][i] = 0 ;for(int k = 1 ; k <= n ; k ++ )for(int i = 1 ; i <= n ; i ++ )for(int j = 1 ; j <= n ; j ++ )dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;
}int main(){int n , m , a , b , c;while( ~ scanf("%d %d" , &n , &m )){memset(edge , inf , sizeof(edge)) ;///memset inf will be the same value//cout << edge[0][0] << endl ;//cout << inf << endl ;for(int i = 0 ; i < m ; i ++ ){scanf("%d %d %d" , &a , &b , &c) ;edge[a][b] = edge[b][a] = c ;}memcpy(dis , edge , sizeof(dis)) ;floyd(n) ;/// number of shortest path from i to jfor(int i = 1 ; i <= n ; i ++ ){for(int j = 1 ; j <= n ; j ++ ){for(int k = 1 ; k <= n ; k ++ ){if(edge[k][j] != inf && dis[i][k] + edge[k][j] == dis[i][j])cnt[i][j] ++ ;}}}for(int i = 1 ; i <= n ; i ++ ){for(int j = i + 1 ; j <= n ; j ++ ){int ans = 0 ;for(int k = 1 ; k <= n ; k ++ ){if(dis[i][k] + dis[k][j] == dis[i][j])ans += cnt[i][k] ;}printf("%d%c" , ans , i < n - 1 ? ' ' : '\n') ;}}}return 0 ;
}