题目大意：有一个，想要在最短的时间內将一个谣言散发给所有人，但是他只能将这个谣言告诉给一个人，，然后通过这个人传播出去。问，他应该告诉哪个人，让所有人都听到这个谣言的最短时间是多少
解题思路：这题很容易想到用floyd求出每个点之间的最短路。 做这题时，已经很久没做最短路的了，所以一时写不出floyd。发现自己太依赖模版了，所以在这里想写一下自己对floyd的理解（借鉴了这里写链接内容）好让自己下次不看模版也能想出来
设dp[i][j]为i到j的最短路，因为floyd有三成for，写起来的时候也知道是i,j,k，也知道j是在i的内部的，关键是k要放在哪里
假设dp[i][j][k]为从i到j的最短路，其中经过的最大中间节点为k，那么就可以得到转移方程 如果不走k这个点，那么dp[i][j][k] = dp[i][j][k-1] 如果走了k这个点，那么dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1] 从上面的观察中，可以得到，更新的时候，第三维的k总是由之前的k－1得来的，所以将其写成滚动数组的形式，将k提取到最外面，那么三层for从外到里就变成了k，i，j了
;g[maxn][maxn];int n;void floyd() {for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(g[i][k] != INF && g[k][j] != INF)g[i][j] = min(g[i][j], g[i][k] + g[k][j]);}void init() {memset(g, 0x3f, sizeof(g));int t, x, y;for(int i = 1; i <= n; i++) {scanf(“%d”, &t);for(int j = 0; j < t; j++) {scanf(“%d%d”, &x, &y);g[i][x] = y;}}floyd();}void solve() {int ans_p, ans_t = INF;for(int i = 1; i <= n; i++) {int Max = 0;for(int j = 1; j <= n; j++) {if(i == j)continue;Max = max(g[i][j], Max);}if(Max < ans_t) {ans_t = Max;ans_p = i;}}if(ans_t == INF)printf(“disjoint\n”);elseprintf(“%d %d\n”, ans_p, ans_t);}int main() {while (scanf(“%d”, &n) != EOF && n) {init();solve();}return 0;}
有一些穿高跟鞋走不到的路，
