有一个图，其中的一些路坏了，为了从a走到b，问最少修复多长的路
输入样例 321 2 12 3 211 21 3 输出样例 1 数据范围2⩽N⩽1002\leqslant N\leqslant 1002⩽N⩽100 N−1⩽D⩽M⩽N∗(N−1)/2N-1\leqslant D\leqslant M\leqslant N*(N-1)/2N−1⩽D⩽M⩽N∗(N−1)/2 1⩽x,y⩽n,x≠y1\leqslant x,y\leqslant n,x\neq y1⩽x,y⩽n,x=y 0<len<1000< len <1000<len<100
解题思路：把坏掉的边的权值保留，其他边改为0，然后直接spfa跑一遍就可以了
代码： #include<queue>#include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,m,k,x,y,z,h,tot,p[150],b[150],head[150],pp[150][150];struct rec{int to,next,l,lon;}a[20500];void spfa()//spfa模板{scanf("%d%d",&x,&y);memset(b,127/3,sizeof(b));queue<int>d;d.push(x);p[x]=1;b[x]=0;while(!d.empty()){h=d.front();d.pop();for (int i=head[h];i;i=a[i].next)if (b[h]+a[i].l<b[a[i].to]){b[a[i].to]=b[h]+a[i].l;if(!p[a[i].to]){p[a[i].to]=1;d.push(a[i].to);}}p[h]=0;}printf("%d",b[y]);return;}int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){scanf("%d%d%d",&x,&y,&z);//连边a[++tot].to=y;a[tot].lon=z;a[tot].next=head[x];head[x]=tot;pp[x][y]=tot;//记下来a[++tot].to=x;a[tot].lon=z;a[tot].next=head[y];head[y]=tot;pp[y][x]=tot;}scanf("%d",&k);for (int i=1;i<=k;++i){scanf("%d%d",&x,&y);a[pp[x][y]].l=a[pp[x][y]].lon;//赋值a[pp[y][x]].l=a[pp[y][x]].lon;}spfa();return 0;}
