๐ฅ Gold4
https://www.acmicpc.net/problem/10282
โ ์ ๋ต ํ์ด
from sys import stdin
from heapq import heappop,heappush
input = stdin.readline
t=int(input())
INF=float('inf')
def dijkstra(start):
dist=[INF]*len(graph)
dist[start]=0
q=[(0,start)]
while q:
cost,idx=heappop(q)
if dist[idx]<cost:
continue
for adj,d in graph[idx]:
if cost+d<dist[adj]:
dist[adj]=cost+d
heappush(q,(dist[adj],adj))
return dist
for _ in range(t):
n,d,c=map(int,input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(d):
a,b,s = map(int, input().split())
graph[b].append((a,s)) # ์ญ๋ฐฉํฅ์ผ๋ก ๋ฃ์ด์ค (์์กด๊ณผ ์ ์ผ์ ์ญ๊ด๊ณ)
#๋ค์ต์คํธ๋ผ
distance=dijkstra(c) # ํดํน๋นํ ์ปดํจํฐ ๊ธฐ์ค ์ต๋จ๊ฑฐ๋ฆฌ ๋ฆฌ์คํธ
result=list(filter(lambda x:x!=INF,distance)) # ๊ฐ์ผ๋ ์ปดํจํฐ=์ธ์
print(len(result),max(result))
โจ ๊ฒฝ๋ก๋ ์๋ฐฉํฅ์ด ์๋์ง๋ง ๊ฐ์ผ์ ์ญ๋ฐฉํฅ์ผ๋ก ํผ์ ธ๋๊ฐ๊ธฐ ๋๋ฌธ์ ๊ทธ๋ํ์ ๊ฐ์ ๋ฃ์ด์ค๋ ์ญ๋ฐฉํฅ์ผ๋ก ๋ฃ์ด์ฃผ๋ฉด ๋๋ค.
๊ทธ๋ ๊ฒ๋๋ฉด, ๊ฐ์ผ๋ ์ปดํจํฐ์ ๊ฐ์๋ ๋ค์ต์คํธ๋ผ ๊ฒฐ๊ณผ๊ฐ์ผ๋ก ์ป์ ์ต๋จ๊ฑฐ๋ฆฌ ์ค ์ด๊ธฐ๊ฐ inf๊ฐ ์๋๊ฐ์ผ๋ก ์ฝ๊ฒ ๊ตฌํ ์ ์๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค ํ ์ค์ ๊ฑธ์ณ ์ด ๊ฐ์ผ๋๋ ์ปดํจํฐ ์, ๋ง์ง๋ง ์ปดํจํฐ๊ฐ ๊ฐ์ผ๋๊ธฐ๊น์ง ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ์ง์ด ์ถ๋ ฅํ๋ค.
๋๋ ๋ง์ง๋ง ์ปดํจ๊ฐ ๊ฐ์ผ๋๊ธฐ๊น์ง ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋ง์ง๋ง ๋ฒํธ(n)๋ฒ ์ปดํจํฐ๊น์ง ๊ฐ์ผ๋๋ ์๊ฐ์ ๊ตฌํ๋๊ฒ์ผ๋ก ์ดํดํ๋ค..๐
๊ทธ๋์ ๊ณ์ distance[n]์ผ๋ก ๊ฐ์ผ๋ ์ปดํจํฐ๋ถํฐ, n๋ฒ๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ถ๋ ฅํ๋ ์ค๋ต์ด ๋์จ๊ฒ์ด์๋คใ ใ
์๋ํ์ง๋ ๋ชฐ๋ผ๋ ํ ์คํธ์ผ์ด์ค๋ง์ ๋ชจ๋ ์ฑ๋ฆฝ๋๊ธธ๋ ๊ณ์ ์ ์๋ผ๋ฅผ ์ธ์น๊ณ ์์๋ค...๐
โ 1์ฐจ ํ์ด
from sys import stdin
from heapq import heappop,heappush
input = stdin.readline
t=int(input())
INF=float('inf')
def dijkstra(start):
dist=[INF]*len(graph)
dist[start]=0
q=[(0,start)]
while q:
cost,idx=heappop(q)
if dist[idx]<cost:
continue
for adj,d in graph[idx]:
if cost+d<dist[adj]:
dist[adj]=cost+d
count[adj]+=count[idx]+1
heappush(q,(dist[adj],adj))
return dist,count
for _ in range(t):
n,d,c=map(int,input().split())
graph = [[] for _ in range(n + 1)]
count=[0]*(n+1)
for _ in range(d):
a,b,s = map(int, input().split())
graph[a].append((b,s)) #(๋
ธ๋๋ฒํธ,cost)
#๋ค์ต์คํธ๋ผ
distance,cnt=dijkstra(n) # ํดํน๋นํ ์ปดํจํฐ ๊ธฐ์ค ์ต๋จ๊ฑฐ๋ฆฌ ๋ฆฌ์คํธ
print(cnt[1],distance[c] if distance[c]!=INF else 0)
์ฒ์ ํ์ดํ๋ ๋ฐฉ์์ ๋ง์ง๋ง ์ปดํจํฐ๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ค์ต์คํธ๋ผ๋ฅผ ํตํด ์ป์ ๊ฑฐ๋ฆฌ ๋ฐฐ์ด์์ ๊ฐ์ผ๋ ์ปดํจํฐ๊น์ง์ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋์์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์๋ค. ๋ฌธ์ ๋ฅผ ์๋ชป ์ดํดํ๊ธฐ ๋๋ฌธ์ ์ถ๋ฐ์ ์ ๋ง์ง๋ง๋ฒํธ ์ปดํจํฐ๋ก ํ๋ฉด๋๊ธฐ์, ์ ๋ฐ ๋ฐฉ์์ ๋ ์ฌ๋ ธ๋ค......
์์ง ์ฒ์ ํ์ด์ ๊ทธ๋ฐ์ง ์ญ๋ฐฉํฅ์ ์๊ฐ์ ๋ฏธ์ฒ ๋ชปํ๋๊ฒ ๊ฐ๋ค. ๋ง์ด ํ์ด๋ณด๋ฉด ๊ด์ฐฎ์์ง๊ฒ ์ง๋ผ๋ ํฌ๋ง์ ๊ฐ์ง๊ณ ํ์ดํ !
'๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-Python] ์ซ์์นด๋ : 10815๋ฒ (0) | 2024.08.03 |
---|---|
[๋ฐฑ์ค-Python] ์ต๋จ๊ฒฝ๋ก : 1753๋ฒ (๋ค์ต์คํธ๋ผ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ) (1) | 2024.06.14 |
[๋ฐฑ์ค-Python] ๊ฑฐ๋ถ์ด : 8911๋ฒ (1) | 2024.06.13 |
[๋ฐฑ์ค-Python] ์๊ธฐ์์ด2 : 17086๋ฒ (0) | 2024.06.13 |
[๋ฐฑ์ค-Python] ํน : 1063๋ฒ (1) | 2024.06.12 |