백준 1753번 최단경로

대놓고 다익스트라 쓰라고 시킨다

 

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

def daijk(end):
    q=[]
    v=[-1]*(n+1)
    heapq.heappush(q,[0,start])
    v[start]=1
    while q:
        cost,cur_v=heapq.heappop(q)
        if cur_v==end:
            print(cost)
            return
        for i in graph[cur_v]:
            if v[i[0]]!=-1:
                continue
            v[i[0]]=cost+i[1]
            heapq.heappush(q,[cost+i[1],i[0]])
    print("INF")
for i in range(1,n+1):
    daijk(i)

작성해줬다.

e가 3*10^5니까 다익스트라인건 맞는데 daijk()을 여러번 호출해서 문제가 되는것같다

내 코드는 O(NELogE)이므로 n이 40000이니까 시간초과가 날수밖에

 

daijk을 n번 호출하지 않게 수정해야한다.

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

q=[]
v=[-1]*(n+1)
heapq.heappush(q,[0,start])
v[start]=0
while q:
    cost,cur_v=heapq.heappop(q)
    for i in graph[cur_v]:
        if v[i[0]]!=-1:
            continue
        v[i[0]]=cost+i[1]
        heapq.heappush(q,[cost+i[1],i[0]])

for i in range(1,n+1):
    if v[i]==-1:
        print("INF")
    else:
        print(v[i])

 

 

이렇게 수정해줬다.

이런경우 반례가 생긴다

그림으로 그리자면

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

q=[]
v=[-1]*(n+1)
heapq.heappush(q,[0,start])

while q:
    cost,cur_v=heapq.heappop(q)
    if v[cur_v]!=-1:
        continue
    v[cur_v]=cost
    for i in graph[cur_v]:
        heapq.heappush(q,[cost+i[1],i[0]])

for i in range(1,n+1):
    if v[i]==-1:
        print("INF")
    else:
        print(v[i])

그래서 이렇게 수정해줬다.

잔실수를 하지 말아야 한다.

if를 for문안에 넣어버렸다...

(해당 값에 처음으로 도달한 순서가 빠른게 중요한게 아니라 해당값을 pop한 순서가 중요한거라서 if가 for안에 있으면 안된다.더 정확히는 cost갱신이 for안에 있으면 안된다.)

이게 싫으면 최소값으로 갱신해주기를 하면되는데

일단은 이렇게 작성했다

 

근데 많이 느리다.

큐에 덜담기 위해서 최소값 갱신으로도 작성해주자 그러면 속도향상이 가능할것이다.

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

q=[]
v=[-1]*(n+1)
heapq.heappush(q,[0,start])
v[start]=0
while q:
    cost,cur_v=heapq.heappop(q)
    
    for i in graph[cur_v]:
        if v[i[0]]!=-1 and v[i[0]]<cost+i[1]:
            continue
        heapq.heappush(q,[cost+i[1],i[0]])
        v[i[0]]=cost+i[1]

for i in range(1,n+1):
    if v[i]==-1:
        print("INF")
    else:
        print(v[i])

이렇게 수정해줬다.

시간초과다

 

그냥 무한루프에 빠지는 경우가 있나보다

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

q=[]
v=[-1]*(n+1)
heapq.heappush(q,[0,start])
v[start]=0
while q:
    cost,cur_v=heapq.heappop(q)
    for i in graph[cur_v]:
        if v[i[0]]!=-1 and v[i[0]]<=cost+i[1]:
            continue
        heapq.heappush(q,[cost+i[1],i[0]])
        v[i[0]]=cost+i[1]
    

for i in range(1,n+1):
    if v[i]==-1:
        print("INF")
    else:
        print(v[i])

작거나 같은으로 수정해줬다.

근데 아직도 느리다.

여기서 더 깎을수가 있다고?

 

import heapq
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
start=int(sys.stdin.readline().rstrip())
graph=[[] for _ in range(n+1)]

for i in range(m):
    u,v,w=map(int,sys.stdin.readline().rstrip().split())
    graph[u].append([v,w])

q=[]
v=[-1]*(n+1)
heapq.heappush(q,[0,start])
v[start]=0
while q:
    cost,cur_v=heapq.heappop(q)
    if v[cur_v]<cost:
        continue
    for i in graph[cur_v]:
        if v[i[0]]==-1 or v[i[0]] > v[cur_v]+i[1]:
            heapq.heappush(q,[cost+i[1],i[0]])
            v[i[0]]=cost+i[1]
    
for i in range(1,n+1):
    if v[i]==-1:
        print("INF")
    else:
        print(v[i])

 

여기서 반정도 더깎은 코드가 존재하지만 솔직히 여기서 더깎는게 가능한가싶다