0、はじめに

最近アルゴリズムを勉強している間に考えていたのですが、解くだけで整理しないので、似たような問題を解くのが大変なので、一日の解を整理して、その日の出来事を整理したいと思います.

朝の散歩

https://www.acmicpc.net/problem/21606
個人的に初めて問題を見たときに思いついたのは屋外を基準に計算することでしたが、正直感覚で撮っただけなので、この考えが合っていないのか、屋外を基準にしても、どのようなコードを作るのは難しいです.
DFSで解くには分類で分かるので基本フレームワークは編成されていますが、正直ここまでです.いくら考えても答えが見つからず、結局見つからなかった.
https://kth990303.tistory.com/141
https://woonys.tistory.com/entry/ジャングル将校学校-22日目-IL-朝-散歩-Phython-位相-ソート-アルゴリズム
問題を解決する方法は,屋外ノードを基準として隣接する室内ノードの漏れ数を中心とする.ノードをさらに整理する過程で,接続するノードが屋内ノードである場合,ノードの順序が異なると異なる経路として扱われるため,経路の数に+2を加えることが重要である.
それに対応する問題を解く時、私の感じは:正直に言って、私の問題に対する理解能力はそんなに悪くなくて、しかもこの問題を解く時、DFS問題はある程度の理解と解答を得ることができると思っていますが、私もこれが極めて個人的な錯覚であることに気づきました.もしかすると、今週が終わる前に、DFSとBFSの問題をできるだけ多く解決すべきだと思います.

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(start, value):
    visited[start] = True
    for i in graph[start]:
        if location[i] == 1:
            value += 1
        elif not visited[i] and location[i] == 0:
            value = dfs(i, value)
    return value


n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
location = [0]+list(map(int, input().strip()))
cnt = 0

for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    if location[a] == 1 and location[b] == 1:
        cnt += 2

hap = 0
for i in range(1, n+1):
    if not visited[i] and location[i] == 0:
        x = dfs(i, 0)
        hap += x*(x-1)

print(cnt + hap)

2.最低コストの獲得

https://www.acmicpc.net/problem/1916
これは多翼点アルゴリズムによって解決する必要がある問題である.
対応するアルゴリズムに関する部分は、羅東彬の講義で学んだ.
https://youtu.be/611B-9zk2o4
最小料金を求めるようなタイプの問題はこれからもたくさん出てくるので、この機会によく知っておいたほうがいいと思いますが、正直一度に理解するのは容易ではなく、何度も同じような問題を繰り返し見るしかありません.
マルチアウトレットアルゴリズムはheapqで実現する場合,時間的複雑度がO(EGV)であり,使用しない場合はO(V^2)であり,時間的複雑度に大きな差があるためheapqで実現する.

from heapq import heappush, heappop
import sys
input = sys.stdin.readline
infinity = int(2e9)


def Dijkstra(start):
    dp[start] = 0
    heap = []
    heappush(heap, [0, start])

    while heap:
        w, n = heappop(heap)
        if dp[n] < w:
            continue
        for x, y in arr[n]:
            z = w + y
            if dp[x] > z:
                dp[x] = z
                heappush(heap, [z, x])


n = int(input())
m = int(input())
arr = [[] for _ in range(n+1)]
dp = [infinity for i in range(n+1)]

for i in range(m):
    start_p, end_p, cost = map(int, input().split())
    arr[start_p].append([end_p, cost])

start, end = map(int, input().split())

Dijkstra(start)
print(dp[end])

でも正直に言うとこっちも答えが见つかりました.後で解いてみます.