結果

問題 No.807 umg tours
ユーザー NoneNone
提出日時 2021-03-12 18:27:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,267 ms / 4,000 ms
コード長 3,740 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 132,956 KB
最終ジャッジ日時 2024-10-14 07:47:25
合計ジャッジ時間 14,992 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
61,184 KB
testcase_01 AC 57 ms
60,800 KB
testcase_02 AC 57 ms
62,720 KB
testcase_03 AC 56 ms
62,848 KB
testcase_04 AC 50 ms
59,904 KB
testcase_05 AC 49 ms
60,032 KB
testcase_06 AC 56 ms
62,336 KB
testcase_07 AC 60 ms
64,256 KB
testcase_08 AC 41 ms
52,608 KB
testcase_09 AC 43 ms
53,248 KB
testcase_10 AC 44 ms
53,120 KB
testcase_11 AC 619 ms
106,496 KB
testcase_12 AC 737 ms
107,816 KB
testcase_13 AC 921 ms
115,488 KB
testcase_14 AC 502 ms
95,040 KB
testcase_15 AC 352 ms
89,596 KB
testcase_16 AC 881 ms
116,372 KB
testcase_17 AC 1,158 ms
126,864 KB
testcase_18 AC 1,146 ms
127,000 KB
testcase_19 AC 1,125 ms
123,056 KB
testcase_20 AC 620 ms
102,744 KB
testcase_21 AC 677 ms
104,948 KB
testcase_22 AC 306 ms
87,420 KB
testcase_23 AC 264 ms
84,968 KB
testcase_24 AC 605 ms
128,764 KB
testcase_25 AC 1,267 ms
132,956 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Graph:

    def __init__(self, n, directed=False, decrement=True, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges = [[] for _ in range(self.n)]
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].append((y, cost))
        if self.directed == False:
            self.edges[y].append((x, cost))

    def dijkstra(self, start=None, INF=10**18):
        """
        返り値は 0-indexed !!!
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        備考: heqpq の比較のための key は第一引数である点に注意( = heappush(heapq, (key,value)) )
        """
        tmp = [INF] * self.n
        res = [INF] * self.n
        if start is None: start=self.decrement
        start=(start-self.decrement,0)
        res[start[0]] = 0
        tmp[start[0]] = 0
        next_set = [(0, start)]
        while next_set:
            dist, pm = heappop(next_set)
            p,m=pm
            if m==1:
                if res[p] < dist:
                    continue
                """ここで頂点pまでの最短距離が確定。よって、ここを通るのはN回のみ"""
                for q, cost in self.edges[p]:
                    temp_d = dist + cost
                    if temp_d < res[q]:
                        res[q] = temp_d
                        heappush(next_set, (temp_d, (q,m)))
            else:
                if tmp[p] < dist:
                    continue
                """ここで頂点pまでの最短距離が確定。よって、ここを通るのはN回のみ"""
                for q, cost in self.edges[p]:
                    temp_d = dist + cost
                    if temp_d < tmp[q]:
                        tmp[q] = temp_d
                        heappush(next_set, (temp_d, (q,m)))
                    if dist < res[q]:
                        res[q] = dist
                        heappush(next_set, (dist, (q,m+1)))

        return tmp,res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.n):
            for y, cost in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement, weight=cost)


        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1')
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

#########################################################
def example():
    global input
    example = iter(
        """
3 3
1 2 1
1 3 1
2 3 3
        """
            .strip().split("\n"))
    input = lambda: next(example)

def example2():
    global input
    example = iter(
        """
5 6
1 2 2
1 3 3
1 4 4
2 5 10
3 5 7
4 5 8

        """
            .strip().split("\n"))
    input = lambda: next(example)

#########################################################
import sys
from heapq import *
input = sys.stdin.readline

# example2()

INF = 10**18  # 大きい数字

N, M = map(int, input().split())

graph = Graph(N, directed=False, decrement=True)
for _ in range(M):
    x, y, cost = map(int, input().split())
    graph.add_edge(x, y, cost)

dist1, dist2 = graph.dijkstra(start=1,INF=INF)

for i in range(N):
    print(dist1[i]+dist2[i])
0