题解 P2683 【小岛】
sukimo
2020-05-17 13:31:54
这道题也算是floyd算法的一个经典变形:增边多源最短路。除了传统的两点间距离外,还会动态地加边。如果每加一条边都要跑一整遍floyd的话,时间复杂度明显难以接受。所以考虑优化。回忆floyd算法的原理,每次都以一个点作为中转点来更新,那么对于每一次增边,只会涉及到两个点,可以先判断是否需要floyd修改(比如没加此边前的两点最短路已经小于边的长度,那么明显加了也没什么用,可忽略),如果需要,就只以它俩为中转点进行更新,这样就优多了。floyd算法的衍生功能实际上是很多的,建议把它的精髓搞懂。
上代码:
```
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;int n,dis[105][105];
void floyd(int x,int y){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][x]+dis[x][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][y]+dis[y][j]);
}
int main(){
int m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i-j)dis[i][j]=INF;
for(int i=1;i<=m;i++){
int type,a,b;scanf("%d%d%d",&type,&a,&b);
if(!type)printf("%d\n",dis[a][b]==INF?-1:dis[a][b]);
else{
int q_edge;scanf("%d",&q_edge);
if(dis[a][b]>q_edge){dis[a][b]=dis[b][a]=q_edge;floyd(a,b);}
}
}
return 0;
}
```