题目描述

blablabla

样例

blablabla

算法1

邻接表

时间复杂度

参考文献

Python 代码

import heapq
import sys
import collections
N = 200020

n,m = map(int, input().split())
e = [0]*N
ne = [0]*N
h = [-1]*N
w = [0]*N
idx = 0
done = [False]*N
dist = [sys.maxsize]*N

def add(a, b, weight):
    global e, ne, w, h, idx
    e[idx] = b
    w[idx] = weight
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

def dijkstra():
    dist[1] = 0
    que = []
    heapq.heappush(que,(0,1))

    while que:
        distance, curnode = heapq.heappop(que)
        if done[curnode]:continue
        done[curnode] = True

        i = h[curnode]
        while i!= -1:
            j = e[i]
            if dist[j] > distance + w[i]:
                dist[j] = distance + w[i]
                heapq.heappush(que, (dist[j], j))
            i = ne[i]
    return -1 if dist[n] == sys.maxsize else dist[n]

if __name__ == "__main__":
    for i in range(m):
        a,b,we = map(int, input().split())
        add(a,b,we)

    t = dijkstra()
    print(t)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla