AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

详解与促背模板 -- 算法基础课 -- 搜索与图论(二):最短路Floyd

作者: 作者的头像   MW10 ,  2025-01-10 16:45:13 ,  所有人可见 ,  阅读 2


1


1
/*
I:(n,m)有向图;
(n,m)有向图,可能重边、自环,边权可能为负;
k个询问,x,y之间的最短距离,若不存在则输出“impossible”
O:每个询问的最小路径长度,不存在则输出“impossible”;

I:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
O:
impossible
1
*/

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

// floyd算法:将图邻接矩阵g[][]转化为最短距离矩阵d[][]
void floyd()
{
    // floyd算法需要邻接矩阵特殊初始化:有权(自己到自己是默认有权),或者INF

    // 经过k:1~n次迭代,更新路径
    // BFS思路可以理解此算法的有效性:初始还不能被更新到,迭代轮数达到后就自然而然更新到
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息