201712 4 ccf c++实现dijkstraspfa算法

题目就不粘贴了 思路:用sum,ans数组分别存储1号结点到每个节点连续走小路的路程,以及1号结点到每个结点的最终疲惫值,疲惫值的计算为如果当前走的是小路,则更新疲惫值以及累计走的小路总和,ans的更新规则为上一结点的疲惫值减去之前走小路累计的疲惫值,然后再加上当前走小路的疲惫值,即 ans[ne]=ans[nn]-sum[nn]sum[nn]+(sum[nn]+next.v)(sum[nn]+next.v),sum更新为当前走小路所累积的路程,即sum[ne]=sum[nn]+next.v,如果走大路,则sum清空为0;ans更新为ans[ne]=ans[nn]+next.v, next.