P7100 [W1] 团

我有一张 $n$ 个节点的无向边带权图。它的边很多，用这个方法表示： - 有 $k$ 个集合；第 $i$ 个集合可以表示为 $S_i=\{(T_1,W_1),(T_2,W_2),\dots,(T_{|S_i|},W_{|S_i|})\}$。 - 对于任何两对 $(T_i,W_i),(T_j,W_j)$ 在同一个集合里面，图中会形成一条连 $T_i$ 和 $T_j$ 的边，边权为 $W_i+W_j$。 请对于所有节点 $i$ 找到 $1$ 到 $i$ 的最短路，即从 $1$ 到 $i$ 的边权和最小的简单路径。

无

无

对于前 $10\%$ 的数据，$|S_i|=2$； 对于前 $20\%$ 的数据，$|S_i|\le10$； 对于前 $50\%$ 的数据，$|N|\le1000,\sum|S_i|\le2000$; 对于 $100\%$ 的数据，$1\le|N|\le2\cdot10^5,\sum|S_i|\le4\cdot10^5,0\le W_i\le10^9$。