求解

链接 直接遍历所有肯定不可行 我们可以尝试dp ,设cnt[i]表示到达i节点的路径数量,sum[i]表示到达路径i所需的时间 那么,对于u->v,代价为w,我们可以得到cnt[v]=cnt[v]+cnt[u] sum[v]=sum[v]+sum[u]+cnt[u]*w 由于u-v有cnt[u]种方式,所以cnt[u]*w 而不是cnt[v]*w 经测试,这题没有多起点的情况,不需要考虑 代码如下: #include<iostream> #include<vector> #include<queue> using namespace std; int ...