模板 - Floyd

void Floyd(){

    for(int k = 1; k <= n; ++k) {

        for(int i = 1; i <= n; ++i) {

            for(int j = 1; j <= n; ++j) {

                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

            }

        }

    }

}

意思是以此使用k作为中转点尝试从k绕路得到新的最短两点距离。

所以只使用其中的一些k，就可以得到不经过其他点的最短路的效果。看起来有点Prim求最小生成树以及匈牙利算法的感觉，是那种可以随时停止的？

https://www.luogu.org/problem/P1119

按时间顺序加入k点，更新最短路。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 205;

int n, m, t[MAXN];

int dis[MAXN][MAXN];

const int INF = 0x3f3f3f3f;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; ++i)

        for(int j = 1; j <= n; ++j)

            dis[i][j] = INF;

    for(int i = 1; i <= n; ++i)

        dis[i][i] = 0;

    for(int i = 1; i <= n; ++i)

        scanf("%d", &t[i]);

    for(int i = 1; i <= m; ++i) {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        ++u,++v;

        dis[u][v] = w;

        dis[v][u] = w;

    }

    int q;

    scanf("%d", &q);

    int curti = 1;

    while(q--) {

        int u, v, T;

        scanf("%d%d%d", &u, &v, &T);

        ++u,++v;

        while(curti <= n && t[curti] <= T) {

            for(int i = 1; i <= n; ++i) {

                for(int j = 1; j <= n; ++j) {

                    dis[i][j] = min(dis[i][j], dis[i][curti] + dis[curti][j]);

                }

            }

            ++curti;

        }

        if(t[u] > T || t[v] > T)

            puts("-1");

        else

            printf("%d\n", dis[u][v] < INF ? dis[u][v] : -1);

    }

    return 0;

}

巴特西

模板 - Floyd

最新文章

热门文章