【AHOI 2015】 小岛 – 最短路

描述

西伯利亚北部的寒地，坐落着由 N 个小岛组成的岛屿群，我们把这些小岛依次编号为 1 到 N 。

起初，岛屿之间没有任何的航线。后来随着交通的发展，逐渐出现了一些连通两座小岛的航线。
例如增加一条在 u 号小岛与 v 号小岛之间的航线，这条航线的用时为 e。 那么沿着这条航线，u 号小岛上的人可以前往 v 号小岛，同样的 v 号小岛上的人也可以前往 u 号小岛，其中沿着这一条航线花费的时间为 e。

同时，随着旅游业的发展，越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。

思路

这题是一题类似 floyd 的题，

我们每次加入一条边时，

就拿这条边来修正其他最短路

拿 u 到 v，修正每一个点i和j

把 i 到 j 拆成 i 到 u 和 v 到 j (或是 i 到 v 和 u 到 j，看哪个小)

也就是说

dis[i][j]=min(dis[i][j],dis[u][v]+min(dis[i][u]+dis[v][j],dis[i][v]+dis[u][j]))

代码

#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 9999999;
int n,m,dis[101][101];
inline void PushEdge(int u,int v,int w) {
    if (dis[u][v] < w) return;
    dis[u][v] = dis[v][u] = w;
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++) {
            int tmp = min(dis[i][u]+dis[v][j],dis[i][v]+dis[u][j]);
            dis[i][j] = min(dis[i][j],tmp+dis[u][v]);
        }
}
int main() {
    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,dispose,u,v;i <= m;i++) {
        scanf("%d%d%d",&dispose,&u,&v);
        if (!dispose) printf("%d\n",dis[u][v] == INF ? -1 : dis[u][v]);
        else {
            int w;
            scanf("%d",&w);
            PushEdge(u,v,w);
        }
    }
    return 0;
}