因为要求是在保证最短路的情况下花费是最小的，所以（先保证最短路设为S吧）
那么花费就是最短路上的新建边条数A+剩余拆掉边的条数B，而且总的原有好的边是一定的，所以，只要使得A尽量小，那么B就大，所以要拆掉的边也会少啦。
所以SPFA以最短路为基础，维护出一个A最小就好。（路径什么的，，from[...]）
1 #include2 #define INF 0x7fffffff 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 #define N 100005 6 using namespace std; 7 inline LL ra() 8 { 9 LL x=0,f=1; char ch=getchar(); 10 while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();} 11 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 12 return x*f; 13 } 14 struct node{ 15 int from,to,next,z; 16 }e[N<<2]; 17 int sum[N<<1],dis[N<<1],head[N<<1],cnt; 18 int q[N<<4],tot1,n,m,from[N<<1]; 19 bool vis[N<<1],inq[N<<1]; 20 void insert(int x, int y, int z) 21 { 22 e[cnt].to=y; 23 e[cnt].from=x; 24 e[cnt].next=head[x]; 25 e[cnt].z=z; 26 head[x]=cnt++; 27 } 28 void SPFA() 29 { 30 for (int i=1; i<=n; i++) sum[i]=dis[i]=inf; 31 sum[1]=dis[1]=0; q[0]=1; int l=0,r=1; from[1]=-1; 32 while (l<=r) 33 { 34 int x=q[l++]; 35 for (int i=head[x];i!=-1;i=e[i].next) 36 { 37 if (dis[e[i].to]==dis[x]+1 && e[i].z==0) 38 { 39 if (sum[e[i].to]>sum[x]+1) 40 { 41 sum[e[i].to]=sum[x]+1; 42 from[e[i].to]=i; 43 if (!inq[e[i].to]) 44 { 45 q[r++]=e[i].to; 46 inq[e[i].to]=1; 47 } 48 } 49 } 50 if (dis[e[i].to]==dis[x]+1 && e[i].z) 51 { 52 if (sum[e[i].to]>sum[x]) 53 { 54 sum[e[i].to]=sum[x]; 55 from[e[i].to]=i; 56 if (!inq[e[i].to]) 57 { 58 q[r++]=e[i].to; 59 inq[e[i].to]=1; 60 } 61 } 62 } 63 if (dis[e[i].to]>dis[x]+1) 64 { 65 dis[e[i].to]=dis[x]+1; 66 from[e[i].to]=i; 67 if (e[i].z==0) sum[e[i].to]=sum[x]+1; 68 else sum[e[i].to]=sum[x]; 69 if (!inq[e[i].to]) 70 { 71 inq[e[i].to]=1; 72 q[r++]=e[i].to; 73 } 74 } 75 } 76 inq[x]=0; 77 } 78 // cout<