jzoj1212. 重建道路

• 题目
• Description
• Input
• Output
• Sample Input
• Sample Output
• 分析
• CODE

题目

Description

Jby在玩一个“辉煌帝国”的网络游戏…
他的帝国有N个城市，城市之前总共有M条道路，每条道路连接两个不同的城市。Jby给出了每条道路的长度。
最近他由于得罪了别的玩家，结果被人家炮轰了一回，好在Jby实力强大，城市都没有被破坏，不过有其中D条道路被破坏了。这将可能导致两个军事重镇A和B之间的通讯，Jby找来了你，要你修复一些被破坏的道路，使得A和B能够重新建立通讯起来，而且由于Jby在这场战争已经用了很多钱了，所以他要求被修复的道路的总长度要最小

Input

第一行有一个整数N（2<=N<=100）,表示有多少个城市。城市的编号是1~N。第二行有一个整数M(N-1<=M<=N*(N-1)/2，表示有多少条道路。接下来有M行，每行3个整数, x,y,len(1<=x,y<=n,x<>y. 0< len <100)表示城市x和城市y有一条长度为len的双向道路。再接下来的一行有一个整数D(1<=D<=M)，表示有D条道路破坏了，然后下面有D行，每行两个整数x，y表示x和y之间的道路被破坏了。 最后一行是两个整数A,B，表示两个重要城市A和B的编号。

Output

仅有一行，代表修复道路的最小费用。

Sample Input

3
2
1 2 1
2 3 2
1
1 2
1 3

Sample Output

1

分析

这其实就是一个非常简单的最短路问题，只需要在A和B之间求被破坏道路的最短路。根据原有的道路系统构建无向图，道路的长度作为无向图的边权，由A到B所经过的那些未被破坏的道路其实是不用代价的，可把它们的边权设为0，注意：不能删去这些边，因为我们可以在这些路上走，只是不需要修复它。在这样一个图里，使用Dijkstra算法或Spfa（等主流最短路算法）求A到B的最短路即可

CODE

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,minn=100000000,ans,a[110][110],f[110][110];
bool b[110][110];

void ss(int x,int y){
	if (x==y){
		minn=min(ans,minn);
	}
	for (int i=1;i<=f[x][0];i++){
		if (b[f[x][i]][0]) continue;
		if (b[x][f[x][i]]) ans+=a[x][f[x][i]];
		b[f[x][i]][0]=1;
		ss(f[x][i],y);
		b[f[x][i]][0]=0;
		if (b[x][f[x][i]]) ans-=a[x][f[x][i]];
	}
	return;
}

int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
		f[x][0]++;
		f[x][f[x][0]]=y;
		f[y][0]++;
		f[y][f[y][0]]=x;
	}
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		b[x][y]=1;
		b[y][x]=1;
	}
	int x,y;
	scanf("%d%d",&x,&y);
	b[x][0]=1;
	ss(x,y);
	printf("%d\n",minn);
	return 0;
}