翻了翻题解,好像没有相类似的(估计我眼瞎)。
就是这样:先普通读入 m 条边:完全普通(使用vector存图)!
接下来的 d 条损坏的边这样处理:
- 读入 u,v。
- 遍历
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即可。