【三种方法】

1.【最简单的弗洛伊德】

【思路】

弗洛伊德的方法 先将有路的点都连接起来 由于只需要修改损坏的点 所以完好的道路是可以走的而且不需要修复 所以消耗为0 可以把损坏的边标记一下 把没被标记的也就是完好的边改为0 因为不需要消耗

最后再跑一遍弗洛伊德就好了

【完整代码】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max = 102;
int f[Max][Max];
bool use[Max][Max];
int main()
{
	int n,m,k;
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(register int i = 1;i <= n;++ i)
		for(register int j = 1;j <= n;++ j)
			f[i][j] = 999;
	for(register int i = 1;i <= m;++ i)
	{
		cin >> x >> y >> z;
		f[x][y] = f[y][x] = z;
	}
	scanf("%d",&k);
	for(register int i = 1;i <= k;++ i)
	{
		cin >> x >> y;
		use[x][y] = use[y][x] = true;
	}
	for(register int i = 1;i <= n;++ i)
		for(register int j = 1;j <= n;++ j)
			if(use[i][j] == false && f[i][j] != 999)
				f[i][j] = 0;
	for(register int k = 1;k <= n;++ k)
		for(register int i = 1;i <= n;++ i)
			for(register int j = 1;j <= n;++ j)
				f[j][i] = f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
	int A,B;
	scanf("%d%d",&A,&B);
	cout << f[A][B] << endl;
	return 0;
}

2.【SPFA】

【思路】

SPFA SPFA诈尸+1 先输入有路的数据 建立边但是先不赋值 保持他默认为0的距离 只把某条边对应的长度稍微记录一下 然后输入坏掉的路 这个时候才将坏掉的路的长度赋值上去 因为完好无损的路可以通过而且不需要耗费去修复 所以对需要修复的路径的总长度没有贡献 就是0 但是坏掉的不一样 贡献它本身的长度

然后跑SPFA求出A到B的最短路就好了

【完整代码】

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int Max = 102;
struct node
{
	int y;
	int ne;
	int z;
}a[Max * Max];
int sum = 0;
int head[Max];
int acioi[Max * Max];
void add(int x,int y,int z)
{
	a[++ sum].y = y;
	a[sum].ne = head[x];
	acioi[sum] = z;
	head[x] = sum;
}

int d[Max];
bool use[Max];
int A,B;
int n,m,k;
void SPFA()
{
	queue<int>q;
	q.push(A);
	for(register int i = 1;i <= n;++ i)
		d[i] = 999;
	d[A] = 0;
	while(!q.empty())
	{
		int qwq = q.front();
		q.pop();use[qwq] = false;
		for(register int i = head[qwq];i != 0;i = a[i].ne)
		{
			int awa = a[i].y;
			if(d[awa] > d[qwq] + a[i].z)
			{
				d[awa] = d[qwq] + a[i].z;
				if(use[awa] == false)
				{
					use[awa] = true;
					q.push(awa);
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(register int i = 1;i <= m;++ i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	scanf("%d",&k);
	for(register int i = 1;i <= k;++ i)
	{
		scanf("%d%d",&x,&y);
		for(register int j = head[x];j != 0;j = a[j].ne)
			if(a[j].y == y)
				a[j].z = acioi[j];
		for(register int j = head[y];j != 0;j = a[j].ne)
			if(a[j].y == x)
				a[j].z = acioi[j];
	}
	scanf("%d%d",&A,&B);
	SPFA();
	cout << d[B] << endl;
	return 0;
}

3.【dijstra】

【思路】

地杰斯特拉+堆优化 我知道的三个求最短路的方法里面貌似生存能力最强的一个 输入数据 处理方式和SPFA的方法一个样 先只把边连接起来但是不赋值边权 让边权保持为0 然后将损坏掉的路赋值上边权 （原因不多赘述了，前面两种方法都说过了）

然后跑dijkstra就好了

【完整代码】

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct point
{
	int w;//按照w从小到大排序 
	int x;
	bool operator < (const point & xx)const 
	{
		return xx.w < w;
	}
};
priority_queue<point>q;
const int Max = 102;
struct node
{
	int y,ne,z;
}a[Max * Max];
int sum = 0;
int head[Max];
int acioi[Max * Max];
int n,m;
int A,B;
int dis[Max];
bool use[Max];

void add(int x,int y,int z)
{
	a[++ sum].y = y;
	a[sum].ne = head[x];
	acioi[sum] = z;
	head[x] = sum;
}

void dj()
{
	dis[A] = 0;
	q.push((point){0,A});
	while(!q.empty())
	{
		point qwq = q.top();
		q.pop();
		int x = qwq.x;
		if(use[x] == true)
			continue;
		else
			use[x] = true;
		for(register int i = head[x];i != 0;i = a[i].ne)
		{
			int awa = a[i].y;
			if(dis[awa] > dis[x] + a[i].z)
			{
				dis[awa] = dis[x] + a[i].z;
				if(use[awa] == false)
					q.push((point){dis[awa],awa});
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(register int i = 1;i <= n;++ i)
		dis[i] = 999;
	int x,y,z;
	for(register int i = 1;i <= m;++ i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	int k;
	scanf("%d",&k);
	for(register int i = 1;i <= k;++ i)
	{
		scanf("%d%d",&x,&y);
		for(register int j = head[x];j != 0;j = a[j].ne)
			if(a[j].y == y)
				a[j].z = acioi[j];
		for(register int j = head[y];j != 0;j = a[j].ne)
			if(a[j].y == x)
				a[j].z = acioi[j];
	}
	scanf("%d%d",&A,&B);
	dj();
	cout << dis[B] << endl;
	return 0;
}

老师代码：

#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
struct edge{
	int x, y, w, pre;
}e[10010];
int elen, last[110];
int d[110], st, ed;
bool destroy[110][110], v[110];

void ins(int x, int y, int w) {
	e[++elen] = edge{x, y, w, last[x]};
	last[x] = elen;
}

void spfa() {
	deque<int> dq;
	dq.push_back(st);
	v[st] = true;
	d[st] = 0;
	while(!dq.empty()) {
		int x = dq.front();
		for(int k=last[x]; k; k=e[k].pre) {
			int y = e[k].y;
			int temp = 0;
			if(destroy[x][y])	temp = e[k].w;
			if(d[y] > d[x] + temp) {
				d[y] = d[x] + temp;
				if(!v[y]) {
					v[y] = true;
					dq.push_back(y);
				}
			}
		}
		dq.pop_front();
		v[x] = true;
	}
	if(d[ed] == d[0])	printf("-1\n");
	else 				printf("%d\n", d[ed]);
}

int main() {
	int n, m, dd;
	while(scanf("%d%d", &n, &m) != EOF) {
		elen = 0;
		memset(last, 0, sizeof(last));
		memset(destroy, false, sizeof(destroy));
		memset(v, false, sizeof(v));
		memset(d, 0x3f, sizeof(d));
		while(m--) {
			int x, y, w;
			scanf("%d%d%d", &x, &y, &w);
			ins(x, y, w);
			ins(y, x, w);
		}
		scanf("%d", &dd);
		while(dd--) {
			int x, y;
			scanf("%d%d", &x, &y);
			destroy[x][y] = true;
			destroy[y][x] = true;
		}
		scanf("%d%d", &st, &ed);
		spfa();
	}
	return 0;
}