题目链接:Click
here~~
题意:
给定 n 个点 m 条边的无向图,求出对于所有的 pair(s,t),图中有多少条边位于 s 到 t 的最短路径上。
思路:
观察数据范围有 500 个点,先跑 floyd ,得出 d[i][j] 代表 i 到 j 的最短路径长度。
再用 dp[i][j] 表示有多少条与 i 相邻的边位于从 i 到 j 的最短路径上。
最后对于 ans[i][j],枚举可能成为从 i 到 j 的最短路径的中间点 k,ans[i][j] = sigma{ dp[k][j] }。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 5e2 + 5; int n,d[N][N],c[N][N],dp[N][N]; void floyd() { memcpy(d,c,sizeof(c)); for(int i=1;i<=n;i++) d[i][i] = 0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } int main() { int m; scanf("%d%d",&n,&m); memset(c,0x3f,sizeof(c)); const int inf = c[0][0]; while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); c[u][v] = c[v][u] = w; } floyd(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { if(c[i][j] != inf && d[i][k] == c[i][j] + d[j][k]) { ++dp[i][k]; } } } 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(d[i][j] == d[i][k] + d[k][j]) ans += dp[k][j]; printf("%d%c",ans,(i==n-1 && j==n) ? '\n' : ' '); } return 0; }