牛客网--KY107 最短路径(Dijkstra)

叁歲伎倆 2022-09-05 00:10 136阅读 0赞

## 问题描述 ##

N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。

## 输入描述 ##

第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路 接下来M行两个整数，表示相连的两个城市的编号。

## 输出描述 ##

N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。

## 示例 ##

> 输入：  
> 4 4  
> 1 2  
> 2 3  
> 1 3  
> 0 1  
> 输出：  
> 8  
> 9  
> 11

## 分析 ##

题意是求单源点到其它点的最短路径，自然而然想到Dijkstra算法。由于M较大，所以采用python：

## 代码 ##

# -*- coding: utf-8 -*-
    """ @Time ： 2021/8/14 23:32 @Author ：KI @File ：dijkstra.py @Motto：Hungry And Humble """
    
    import os
    import math
    import sys
    
    n, m = 0, 0
    res = []
    MAX = 0
    
    
    def dijkstra():
        visited = [0] * n
        dis = [MAX] * n
        for i in range(n):
            dis[i] = res[0][i]  # 初始化
        visited[0] = 1  # 初始点访问
        dis[0] = 0
        for t in range(n - 1):
            _min = MAX
            k = -1
            for i in range(1, n):
                if visited[i] == 0 and dis[i] < _min:
                    _min = dis[i]
                    k = i
            if k == -1:  # 非连通的
                return dis
            visited[k] = 1
    
            for j in range(0, n):
                if dis[k] + res[k][j] < dis[j]:
                    dis[j] = dis[k] + res[k][j]
        return dis
    
    
    if __name__ == '__main__':
        n, m = map(int, input().split())
        MAX = (1 << 501) * m
        res = [[MAX for col in range(n)] for row in range(n)]
        # print(res)
        for i in range(m):
            x, y = map(int, input().split())
            if res[x][y] != MAX:
                continue
            # print('当前输入：', x, y)
            res[x][y] = 1 << i
            res[y][x] = 1 << i
        for i in range(n):
            res[i][i] = 0
        # for i in range(len(res)):
        # print(res[i])
        x = dijkstra()
        for i in range(1, n):
            if x[i] != MAX:
                print(x[i] % 100000)
            else:
                print(-1)

## 坑 ##

本题的输入数据有一些坑：  
  测试数据中会有重复输入，比如83 53就输入了三遍，感觉不太能理解。所以在对邻接矩阵初始化时需要作出判断并跳过。