백준 13907 세금 (python)

문제 링크

https://www.acmicpc.net/problem/13907

13907번: 세금

 

아이디어

N이 1000이다. 따라서 floyd가 아닌 다익스트라를 쓰는건 확실하다.

세금이 인상될때 마다 다익스트라를 쓴다면?

pq를 쓰는 다익스트라를 쓴다고 해도 O(K * (M + N)logN)은 썩 좋아 보이지 않는다.

다른 풀이가 필요하다.

우선 세금이 없는 경우 S->D의 특정 경로의 통행료를 A라하자. 이때 거친 간선의 수를 B라하면

세금이 x원 부과된 경우 통행료는 A + B * x이다.

이식을 최소로 하기 위해선

1. 통행료가 같다면 거친 간선의 수가 최소인 것이 최적이다.

2. 거친 간선의 수가 같다면 통행료가 최소인 것이 최적이다.

라는 생각을 할 수 있다.

(이 생각으로 풀이는 여러개 나올거 같긴 하다.)

 

풀이

우선 세금이 없을때도 구해야하므로 그건 그냥 구해도 된다.

나는 한번에 다~ 구할 것이다.

path라는 것을 선언한다. path[node][lv]는 간선을 lv만큼 거쳤을때 S->node의 최소 통행비이다.

(난 완전 그래프가 아닌 이상 노드까지 도달하기에 거치는 간선수는 한정적일 것이라 보고 hash table(dictionary)로 선언했으나 2차원 배열(리스트)도 상관없을 것이다.)

S -> node의 최소 통행비가 X이고 간선을 L만큼 거쳤다고 하자.

우리는 S -> node 경로의 통행비가 X보다 큰 주제에 거친 간선도 L이상이면 그건  굳이 필요없음을 유념해야 한다.

bfs에 기반한 다익스트라(최적화 안한 다익스트라)를 쓴다면

1. 간선을 적게 쓸때 통행료

2. 최소 통행료

둘다 구해줄 수 있다.

그렇게 다익스트라를 돌리고

path[D]에는 우리가 필요한 간선을 lv개 썻을때 최소통행료 정보가 들어있다.

그걸로 세금을 처리하면 된다. A + B * x

 

코드

import sys
from collections import deque

 

input = sys.stdin.readline
N, M, K = map(int, input().split())
S, D = map(int, input().split())
g = {n: [] for n in range(1, N + 1)}
for _ in range(M):
    a, b, w = map(int, input().split())
    g[a].append((b, w))
    g[b].append((a, w))
for n in range(1, N + 1):
    g[n].sort(reverse=True)
q = deque([(0, S, 0)])
distance = [float('inf')] * (N + 1)
distance[S] = 0
path = {i: {} for i in range(1, N + 1)}
path[S][0] = 0
while q:
    dist, node, level = q.popleft()
    for n, d in g[node]:
        tmp = dist + d
        lv = level + 1
        if lv in path[n]:
            if path[n][lv] > tmp:
                path[n][lv] = tmp
        else:
            if tmp < distance[n]:
                path[n][lv] = tmp
        if distance[n] > tmp:
            distance[n] = tmp
            q.append((tmp, n, lv))
print(distance[D])
for _ in range(K):
    current = float('inf')
    k = int(input())
    for l in path[D]:
        path[D][l] += l * k
        current = min(current, path[D][l])
    print(current)