結果

問題 No.1301 Strange Graph Shortest Path
ユーザー NoneNone
提出日時 2021-04-18 18:30:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,840 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 87,104 KB
実行使用メモリ 131,496 KB
最終ジャッジ日時 2023-09-17 07:55:31
合計ジャッジ時間 24,567 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
71,524 KB
testcase_01 AC 79 ms
71,100 KB
testcase_02 WA -
testcase_03 AC 555 ms
114,088 KB
testcase_04 AC 760 ms
129,872 KB
testcase_05 AC 491 ms
115,184 KB
testcase_06 AC 701 ms
124,424 KB
testcase_07 AC 675 ms
121,028 KB
testcase_08 AC 577 ms
113,876 KB
testcase_09 AC 680 ms
122,248 KB
testcase_10 WA -
testcase_11 AC 714 ms
124,576 KB
testcase_12 AC 698 ms
126,552 KB
testcase_13 AC 663 ms
119,016 KB
testcase_14 AC 696 ms
121,320 KB
testcase_15 AC 684 ms
120,952 KB
testcase_16 AC 764 ms
130,688 KB
testcase_17 AC 668 ms
121,132 KB
testcase_18 AC 625 ms
118,740 KB
testcase_19 AC 706 ms
126,124 KB
testcase_20 AC 703 ms
126,056 KB
testcase_21 AC 679 ms
121,272 KB
testcase_22 AC 691 ms
127,728 KB
testcase_23 AC 677 ms
121,164 KB
testcase_24 AC 711 ms
126,588 KB
testcase_25 AC 732 ms
127,140 KB
testcase_26 AC 685 ms
122,208 KB
testcase_27 AC 702 ms
124,812 KB
testcase_28 AC 565 ms
115,948 KB
testcase_29 WA -
testcase_30 AC 740 ms
126,928 KB
testcase_31 AC 735 ms
127,568 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 654 ms
130,592 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)) )
        """
        self.parent=parent=[-1]*N
        res = [INF] * self.n
        if start is None: start=self.decrement
        start=start-self.decrement
        res[start] = 0
        next_set = [(0, start)]
        while next_set:
            dist, p = heappop(next_set)
            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
                    parent[q] = p
                    heappush(next_set, (temp_d, q))

        return res

    def path_restoring(self,start,goal):
        start,goal=start-self.decrement,goal-self.decrement
        q=goal
        res=[]
        while q!=start:
            res.append(q+self.decrement)
            q=self.parent[q]
            if q<0: return -1
        res.append(start+self.decrement)
        return res[::-1]


    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(
        """
6 9
1 2 7
2 3 10
1 3 9
1 6 14
3 6 2
5 6 9
4 5 6
2 4 15
3 4 11
        """
            .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)

data=[]

for _ in range(M):
    x, y, cost, cost2 = map(int, input().split())
    graph.add_edge(x, y, cost)
    data.append((x,y,cost,cost2))

dist = graph.dijkstra(start=1,INF=INF)
path=graph.path_restoring(1,N)

used=set()

for i in range(len(path)-1):
    used.add((path[i],path[i+1]))
    used.add((path[i+1],path[i]))

graph2 = Graph(N, directed=False, decrement=True)

for x, y, cost, cost2 in data:
    if (x,y) in used:
        graph2.add_edge(x, y, cost2)
    else:
        graph2.add_edge(x, y, cost)

dist2 = graph2.dijkstra(start=1,INF=INF)

print(dist[-1]+dist2[-1])
0