【模板】单源最短路1

[编程题]【模板】单源最短路1

热度指数：13345 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 1 ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.

输入描述:

第一行两个整数n和m，表示图的点和边数。
接下来m行，每行两个整数u，v，表示u到v有一条无向边。

输出描述:

输出一行，表示1到n的最短路，如不存在，输出-1.

示例1

输入

输出

示例2

输入

输出

-1

说明

1号点不能到4号点。

算法知识视频讲解

Python 3

TS9527

BFS可以直接解决。

一开始漏看了这个题是无向图，还在按有向图做，结果怎么都过不了。换成无向图之后就会了

class MainActivity:

    def main(self):
        # Read the data
        n, m = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
        edges = dict()
        for _ in range(m):
            u, v = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
            u -= 1
            v -= 1
            if u in edges:
                edges[u].add(v)
            else:
                edges[u] = {v}
            if v in edges:
                edges[v].add(u)
            else:
                edges[v] = {u}
        # Initialization
        visited = [0] * 5000
        candidates = [0]
        # Traverse
        cnt = 0
        while candidates:
            nextCandidates = []
            for candidate in candidates:
                if candidate == n - 1:
                    print(cnt)
                    return
                visited[candidate] = 1
            for candidate in candidates:
                for nextNode in edges.get(candidate, set()):
                    if not visited[nextNode]:
                        nextCandidates.append(nextNode)
            candidates = nextCandidates
            cnt += 1
        print(-1)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-06 13:31:15 回复(0)