P3905 道路重建

题目描述

从前，在一个王国中，在\(n\)个城市间有\(m\)条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有\(d\)条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市\(A\)和\(B\)之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使\(A\)与\(B\)之间的连接恢复，并要求修复的道路长度最小。

输入格式

输入文件第一行为一个整数\(n（2<n≤100）\),表示城市的个数。这些城市编号从\(1\)到\(n\)。

第二行为一个整数\(m（n-1≤m≤\frac{1}{2} n(n-1)）\)，表示道路的数目。

接下来的\(m\)行，每行\(3\)个整数\(i,j,k（1≤i,j≤n,i≠j,0<k≤100）\)，表示城市\(i\)与\(j\)之间有一条长为\(k\)的道路相连。

接下来一行为一个整数\(d（1≤d≤m）\)，表示战后被破坏的道路的数目。在接下来的\(d\)行中，每行两个整数\(i\)和\(j\)，表示城市\(i\)与\(j\)之间直接相连的道路被破坏。

最后一行为两个整数A和B，代表需要恢复交通的两个重要城市。

输出格式

输出文件仅一个整数，表示恢复\(A\)与\(B\)间的交通需要修复的道路总长度的最小值。

输入输出样例

输入 #1

3

2

1 2 1

2 3 2

1

1 2

1 3

输出 #1

【三种方法】

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;

}

巴特西

洛谷 P3905 道路重建题解

P3905 道路重建

题目描述

输入格式

输出格式

输入输出样例

【三种方法】

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

【思路】

【完整代码】

2.【SPFA】

【思路】

【完整代码】

3.【dijstra】

【思路】

【完整代码】

最新文章

热门文章

巴特西

洛谷 P3905 道路重建 题解

P3905 道路重建

题目描述

输入格式

输出格式

输入输出样例

【三种方法】

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

【思路】

【完整代码】

2.【SPFA】

【思路】

【完整代码】

3.【dijstra】

【思路】

【完整代码】

最新文章

热门文章

洛谷 P3905 道路重建题解