大牛的解题报告没看明白，自己猜了下（ 在解题报告后面 ），不知道是不是这个意思。各位AC了的大大能不能帮帮忙看看.

1006:
暴力算法：枚举每条边，然后对每个点求一次单源最短路，由于题目中的边的权值都是1，因此可以用bfs来求得每个点的单源最短路。复杂度是O(M*N*M)。由于M*N*M=3000*100*3000=9*10^8,
因此只能通过数据规模较小的测试数据。
标程算法：仍然使用上面的思路，但要作一些预处理。对每个顶点u求一次单源最短路，把求得的结果称作u的最短路径树。若被破坏的公路不在该最短路径树上，则从u出发的所有最短路径的总和就是u到该树上的所有顶点的路径的总和，这里可以作O(M)的预处理，然后花费O(1)时间就能返回结果；否则，删除被破坏的公路后，从新计算从u出发的所有最短路径的总和，这步的复杂度是O(M)。由于最短路径树上只有N-1条边，因此需要从新计算的次数只有N-1次。因此，程序的复杂度变为O(N*N*M)=3*10^7。

我自己按照解题报告猜的.
N个点，M条边
猜的： 对于一颗无向连通图，每条边的长度为1，那么以点u出发到其它所有点的最短路径组成的树 等于 从点u出发的最小生成树.
1、对一个点u， bfs一次求出u到剩下的N-1个点的最短距离，同时记录这颗树。 O(M)的时间。 有N个点，所以O(N*M) .
2、在1中记录的每个点u的最短路径树中只有N-1条边(因为是最小生成树),所以M次删边操作中只会有N-1次对点u有影响(需要重新从点u计算最短路径树), 重新计算需要O(M)的时间, 所以对于每个点u，最多O( (N-1)*M )次, N个点，所以 O( N*(N-1)*M ) 次。再加上1的时间，总复杂度 O( N*N*M ) .