本文主要是介绍CodeForces 416E President's Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
求图中任意两点间在最短路上的道路条数
思路：
floyd最短路 因为 dis[u][v] = dis[u][i] + edge[i][j] + dis[j][v] 枚举需要N^4所以需要优化
用培根大爷的话说就是利用了DP前缀和的思想
枚举边 如果dis[i][v] = edge[i][j] + dis[j][v] 那么edge在i到v的最短路上
记录cnt[i]表示i到v的最短路上与i想接的路的条数
那么求出cnt后 枚举起点i和中点k 如果dis[i][j] = dis[i][k] + dis[k][j] 则ans[i][j] += cnt[k]
理解一下就是i到j的最短路上的所有点k 挨着k（挨着这一性质可以防止重复计数）的且在k到j的最短路上的路的数量的和
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 510
#define oo 2147483647int n,m;
int maz[M][M],ans[M][M];
int cnt[M];
struct edge
{int u,v,w;
}ed[M*M];int main()
{int i,j,k;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){for(j=1;j<=n;j++) maz[i][j]=oo;maz[i][i]=0;}for(i=1;i<=m;i++){scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);maz[ed[i].u][ed[i].v]=maz[ed[i].v][ed[i].u]=ed[i].w;}for(k=1;k<=n;k++){for(i=1;i<=n;i++){if(i==k||maz[i][k]==oo) continue;for(j=1;j<=n;j++){if(j==i||j==k||maz[k][j]==oo) continue;maz[i][j]=min(maz[i][j],maz[i][k]+maz[k][j]);}}}for(j=1;j<=n;j++){memset(cnt,0,sizeof(cnt));for(i=1;i<=m;i++){if(maz[ed[i].u][j]==maz[ed[i].v][j]+ed[i].w) cnt[ed[i].u]++;if(maz[ed[i].v][j]==maz[ed[i].u][j]+ed[i].w) cnt[ed[i].v]++;}for(i=j-1;i>=1;i--){for(k=1;k<=n;k++){if(maz[i][k]+maz[k][j]==maz[i][j]) ans[i][j]+=cnt[k];}}}for(i=1;i<=n;i++){for(j=i+1;j<=n;j++) printf("%d%s",ans[i][j],(i==n-1&&j==n)?"\n":" ");}return 0;
}
这篇关于CodeForces 416E President's Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
