题目
Luogu P3905 道路重建
分析
使得修复总长度为最小，即使得两点之间路径为最短。因为AB两点现在没有被连接，所以只要修复最短路径上需要修复的路，即可联通，并且答案最小（这是显然的）。
假定全部道路通畅，跑一遍A到B的最短路，然后将被毁坏的道路边权设为0，再跑一遍最短路。两次所得的B的最短路之差，就是最短路径上需要修复的路的长度。路径上某些边的权变成0后，再得的最短路只会变得更短或者不变（这条路径上没有需要修复的，此时答案为0）。
代码
#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=500002,inf=2147483647;
//边至少要开2倍：因为是无向边，连接两相同节点的边要加两次，所以理论最大边数为n(n-1)≈n^2，因此理论最大被毁坏边数为n^2，此处多开了一些，并无影响；
struct Edge{int to,next,v;
}e[maxn];//建立边表；
int head[maxn],dis[maxn],a[maxn],b[maxn];
bool vis[maxn];
queue<int>q;
int n,m,d,s,t,cnt;
void add(int u,int v,int w)//链式前向星存图；
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;
}
void spfa()//采取spfa求AB之间的最短路，当然也可以用dijkstra等；
{for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;dis[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dis[v]>dis[u]+e[i].v){dis[v]=dis[u]+e[i].v;if(!vis[v]){vis[v]=1;q.push(v);}}}}
}
int main()
{int x,y,z,ans;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);//无向边。}scanf("%d",&d);for(int i=1;i<=d;i++)scanf("%d%d",&a[i],&b[i]);//由于需要起点和终点，所以要保存起来，输入起点终点后再使用；scanf("%d%d",&s,&t);spfa();ans=dis[t];//ans为假定畅通时的长度；for(int i=1;i<=d;i++){add(a[i],b[i],0);add(b[i],a[i],0);//可以直接加边的原因是，根据spfa的原理，两点之间即使有多条边，最终都将被更新为最短的那一条；}spfa();ans-=dis[t];//此时的ans就是答案了；printf("%d",ans);return 0;
}