1. 题目

传送门= ̄ω ̄=
题目大意:给你一张有向图,求点1到其他点和其他点到点1的最短路长度之和。
节点数、边数在10^6以内

题解

此题卡常。
用真正链表会超时,因为真链表会动态申请空间。
stl更不用说。
得用模拟链表。

至于思路,很简单,建立反向图,在原图、反向图上分别跑一下spfa。
最后求最短路之和。

代码: