반응형
1. 문제
https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
2. 풀이
다익스트라.
단방향이기 때문에 갈 때와 올때의 길이 다르고 두 값을 더한 것의 최대값을 구해야한다.
3. 구현
import sys
import heapq
import math
# sys.stdin=open("input.txt")
N, X, T = map(int, sys.stdin.readline().split())
def dijk(start, end, gph):
dist=[math.inf for _ in range(N+2)]
edges=[]
dist[start]=0
heapq.heappush(edges,(dist[start],start))
while edges:
cost,pos = heapq.heappop(edges)
for p,c in gph[pos]:
c+=cost
if dist[p]>c:
dist[p]=c
heapq.heappush(edges,(c,p))
return dist[end]
gph=[[] for _ in range(N+2)]
gph_back=[[] for _ in range(N+2)]
while X:
X-=1
a,b,c = map(int, sys.stdin.readline().split())
gph[a].append((b,c))
gph_back[b].append((a,c))
m=0
for idx in range(N):
m = max(m,dijk(idx+1,T,gph)+dijk(T,idx+1,gph))
print(m)
4. 추가 테스트케이스
10 24 2
9 5 9
7 9 2
8 1 7
7 10 2
6 1 6
10 6 5
5 1 6
5 7 9
3 8 9
4 10 7
8 10 6
7 2 6
4 3 1
10 9 9
8 5 9
2 1 4
3 9 6
1 2 4
8 3 3
1 8 4
8 7 8
6 8 5
1 4 2
2 3 4답 29
7 21 4
1 2 7
7 3 7
6 5 1
6 7 9
3 6 9
2 3 4
3 5 8
2 7 5
4 1 3
1 3 3
6 2 8
2 5 1
4 3 1
5 4 2
5 1 1
3 2 6
6 3 3
5 7 8
2 6 6
1 6 3
3 1 9답 28
반응형
댓글