题解 P2683 【小岛】

这道题也算是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; } ```