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
【三种方法】
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;
}