这道题一个新的想法
查看原帖
这道题一个新的想法
747475
SnapYust楼主2022/10/26 23:25

翻了翻题解,好像没有相类似的(估计我眼瞎)。

就是这样:先普通读入 mm 条边:完全普通(使用vector存图)!

接下来的 dd 条损坏的边这样处理:

  • 读入 uuvv
  • 遍历vector数组,寻找这条边。
  • 找到之后把这条边存到邻接矩阵,即:
g[u][v] = w, g[v][u] = w;
  • 继续循环。

处理完了之后,跑一边dijkstra(注意存储路径)。

接下来遍历路径,这样:

for (int i = 0; i < Path.size() - 1; i++) ans += g[Path[i]][Path[i + 1]];

然后输出ans即可。

2022/10/26 23:25
加载中...