题目大意

链接
有n个点，m条路，其中每条路有边权。最初每个点直接是连通的，经过时不需要花费代价，但其中有d条路被破坏了，经过时的代价就是它的边权，求从a点到b点的最小代价。

解题思路

如果两条边直接有路就设$f_{i,j}$为0，被破坏了就设$f_{i,j}$为$g_{i,j}$，n$\le 100$跑Floyd都能过。

一定要建双向边！！！

代码（写的很丑陋

#include
using namespace std;
int f[105][105],a[105][105],n,m,d;
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			f[i][j]=1e5;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		cin>>a[x][y];
		a[y][x]=a[x][y];
		f[x][y]=f[y][x]=0;
	}
	cin>>d;
	for(int i=1;i<=d;i++)
	{
		int x,y; 
		cin>>x>>y;
		f[x][y]=f[y][x]=a[x][y];
	}
	int x,y;
	cin>>x>>y;
	for(int k=1;k<=n;k++)
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
		if(f[i][k]+f[k][j]<f[i][j])
			f[i][j]=f[i][k]+f[k][j];
	cout<<f[x][y];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38