题意： 求图中任意两点间在最短路上的道路条数 思路： 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]表示

E. President and Roads time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Berland has n cities, the capital is located in

目录 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 Problem - 567E - Codeforces 二、解题报告 1、思路分析 警钟敲烂——注