Road to Savings[백준 27617]

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

 

 

 

최단경로가 되는 경로를 모두 저장하고 전체 경로에서 최단경로에 포함 안 되는 것들을 찾으면 된다. 

import heapq

def dijkstra(start, n, gra):
    dp = [float('inf')] * (n + 1)
    dp[start] = 0
    heap = [(0, start)]
    parent = [[] for _ in range(n + 1)]  
    while heap:
        wei, now = heapq.heappop(heap)
        if dp[now] < wei:            continue
    
        for node, cost in gra[now]:
            next_wei = cost + wei
            if next_wei < dp[node]:
                dp[node] = next_wei
                parent[node] = [now]  
                heapq.heappush(heap, (next_wei, node))
            elif next_wei == dp[node]:
                parent[node].append(now) 
    
    return dp, parent

def find_paved_roads(node, parent, visited):
    paved = set()
    def dfs(v):
        for u in parent[v]:
            if (min(u, v), max(u, v)) not in visited:
                # print(u,v )
                visited.add((min(u, v), max(u, v)))
                paved.add((min(u, v), max(u, v)))
                dfs(u)
    dfs(node)
    return paved

def main():
    n, m, a, b = map(int, input().split())
    gra = [[] for _ in range(n + 1)]
    total = 0
    
    roads = []
    for _ in range(m):
        i1, i2, l = map(int, input().split())
        gra[i1].append((i2, l))
        gra[i2].append((i1, l))
        roads.append((min(i1, i2), max(i1, i2), l))
        total += l
    
    dp, parent = dijkstra(a, n, gra)
    # print(dp)
    # print(parent) 
    
    visited = set()
    paved_roads = find_paved_roads(b, parent, visited)
    unnecessary_road_length = 0
    for i1, i2, l in roads:
        if (i1, i2) not in paved_roads:
            unnecessary_road_length += l
    
    print(unnecessary_road_length)

if __name__ == "__main__":
    main()