見たいPythonアレンジ


  • 李可泰映像参考
    入力
    2 D配列の入力
    graph = [[int(x) for x in sys.stdin.readline().split()] for y in range(m)]    
    arr = [[0 for i in range(m)] for i in range(n)]
    n個string入力
    data = [sys.stdin.readline().strip() for i in range(n)]
    少数の判別
    import math
    
    # 소수 판별 함수
    def is_prime_number(x):
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        return True
    エラトステネスのふるい
    def prime_list(n):
        sieve = [True] * n
    
        m = int(n ** 0.5)
        for i in range(2, m + 1):
            if sieve[i] == True: 
                for j in range(i+i, n, i):
                    sieve[j] = False
    データ構造
    Defaultdict
    from collections import defaultdict
    d = defaultdict(int) # int, list, set 다 가능
    優先キュー1(heapq)
    import heapq
    que = []
    heapq.heappush(que, i)
    j = heapq.heappop(que)
  • queue.PriorityQueue()の速度はthread safeより遅い.カラオケでheapqを使いましょう
  • アルゴリズム#アルゴリズム#
    位相位置合わせ
    from collections import deque
    
    v, e = map(int, input().split())
    indegree = [0]*(v+1)
    graph = [[] for i in range(v+1)]
    
    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        indegree[b] += 1
    
    def topology_sort():
        result=[]
        q = deque()
        for i in range(1, v+1):
            if indegree[i]==0:
                q.append(i)
        while q:
            now = q.popleft()
            result.append(now)
            for i in graph[now]:
                indegree[i] -= 1
                if indegree[i] ==0:
                    q.append(i)
        for i in result:
            print(i, end=' ')
    
    topology_sort()
    ツリー巡り
    class Node:
        def __init__(self, data, left_node, right_node):
            self.data = data
            self.left_node = left_node
            self.right_node = right_node
    # 전위 순회
    def pre_order(node):
        print(node.data, end='')
        if node.left_node != None:
            pre_order(tree[node.left_node])
        if node.right_node != None:
            pre_order(tree[node.right_node])
    #중위 순회
    def in_order(node):
        if node.left_node != None:
            in_order(tree[node.left_node])
        print(node.data, end='')
        if node.right_node != None:
            in_order(tree[node.right_node])
    #후위 순회
    def post_order(node):
        if node.left_node != None:
            post_order(tree[node.left_node])
        if node.right_node != None:
            post_order(tree[node.right_node])
        print(node.data, end='')
    
    n = int(input())
    tree = {}
    
    for i in range(n):
        data, left_node, right_node= input().split()
        if left_node ==".":
            left_node = None
        if right_node == ".":
            right_node = None
        tree[data] = Node(data, left_node, right_node)
    
    pre_order(tree['A'])
    print()
    in_order(tree['A'])
    print()
    post_order(tree['A'])
    セグメントツリー
    import sys
    input = sys.stdin.readline
    
    def init(node, start, end): 
        if start == end :
            tree[node] = l[start]
            return tree[node]
        else :
            tree[node] = init(node*2, start, (start+end)//2) + init(node*2+1, (start+end)//2+1, end)
            return tree[node]
     
    
    def subSum(node, start, end, left, right) :
        
        if left > end or right < start :
            return 0
        if left <= start and end <= right :
            return tree[node]
        return subSum(node*2, start, (start+end)//2, left, right) + subSum(node*2 + 1, (start+end)//2+1, end, left, right)
     
    def update(node, start, end, index, diff) :
        if index < start or index > end :
            return
        tree[node] += diff
        if start != end :
            update(node*2, start, (start+end)//2, index, diff)
            update(node*2+1, (start+end)//2+1, end, index, diff)
    n, q = map(int, input().rstrip().split())
    l = []
    tree = [0] * ((4*n))
    l = list(map(int, input().split()))
    
    init(1, 0, n-1)
    そして自分で見てやる
    ベルマンフォード
    構成
  • 開始ノード
  • 最短距離テーブル初期化
  • ステップN-1を繰り返す
  • すべての幹線E,
  • を逐条検査する
  • を通過する各幹線から他のノードへのコストを計算することにより、最短距離テーブル
  • を更新する.
  • 負の幹線ループが発生しているかどうかを確認するには、3番目のプロシージャ
  • を再度実行します.
  • 最短距離表を更新すると、
  • の負の幹線サイクルが存在する.
    import sys
    input = sys.stdin.readline
    INF = int(1e9) # 무한을 의미하는 10억
    
    def BellmanFord(start):
        # 시작 노드에 대해서 초기화
        dist[start] = 0
        # 전체 n번의 라운드를 반복
        for i in range(n):
            # 매 반복마다 "모든 간선"을 확인하며
            for j in range(m):
                cur = edges[j][0]
                next_node = edges[j][1]
                cost = edges[j][2]
                # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                    dist[next_node] = dist[cur] + cost
                    # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                    if i == n-1:
                        return True
        return False
    
    
    n, m = map(int, input().split()) # 노드, 간선의 개수
    edges = [] # 모든 간선에 대한 정보를 담는 리스트
    dist = [INF] * (n+1) # 최단거리 테이블을 모두 무한으로 초기화
    
    # 모든 간선 정보 입력
    for _ in range(m):
        a,b,c = map(int, input().split()) # a노드에서 b노드로 가는 비용이 c
        edges.append((a,b,c))
    
    # 벨만포드 알고리즘 수행
    negative_cycle = BellmanFord(1) # 1번 노드가 시작 노드
    
    if negative_cycle:
        print("-1")
    else:
        # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
        for i in range(2, n+1):
            if dist[i]==INF:
                print("-1")
            else:
                print(dist[i])