import heapq as hq
import sys
input = sys.stdin.readline
INF = float('inf')
N,M = map(int,input().split())
# 간선 정보 받아주기
G = [[] for _ in range(N+1)]
for _ in range(M):
a,b,cost,flavor = map(int,input().split())
G[a].append((b,cost,flavor))
G[b].append((a,cost,flavor))
# 방문처리 배열열
V = [[INF]*(N+1) for _ in range(2)]
V[0][1] = 0
heap = [(0,1,0)]
while heap:
t,x,state = hq.heappop(heap)
# 간선 수가 많아서 최적화필요
if t > V[state][x]:
continue
# 인접 노드 탐색
for nx,cost,flavor in G[x]:
nt = t+cost
# 돈까쓰를 먹지 않는 경우 state를 유지하고 다익스트라
if nt < V[state][nx]:
hq.heappush(heap,(nt,nx,state))
V[state][nx] = nt
# 돈까쓰를 먹을 수 있는 경우 (state == 0), state를 1로 바꿔주고 flavor만큼 감소소
if not state and nt-flavor < V[1][nx]:
hq.heappush(heap,(nt-flavor,nx,1))
V[1][nx] = nt-flavor
for x in range(2,N+1):
print(V[1][x])
import heaheap as hq
inf = 2000000007
V,E = map(int, input().split())
G = [[] for i in range(2*V+1)]
for i in range(E):
x, y, t, k = map(int, input().split())
# 그냥 간선
G[x].append((y, t))
G[y].append((x, t))
# 돈까스 간선
G[x].append((V+y, t-k))
G[y].append((V+x, t-k))
# 그냥 간선
G[V+x].append((V+y, t))
G[V+y].append((V+x, t))
V = [inf for i in range(2*V+1)]
V[1] = 0
heap = [(0,1)]
while heap:
t, x = hq.heappop(heap)
if V[x] != t:
continue
for nx,cost in G[x]:
nt = t + cost
if nt < V[nx]:
V[nx] = nt
hq.heappush(heap, (nt, nx))
for i in range(2, V+1):
print(V[V+i])
다른 사람 풀이 정리
핵심 로직 : state를 나누지 않고 정점을 2배로 늘림 (돈까스를 먹은 상태/안먹은 상태)
그래프 간선도 3배로 늘려서 풀이
돈까스를 먹지 않으면서 이동하는 간선 (돈까스 안먹은 상태)
돈까스를 먹으면서 이동하는 간선
돈까스를 먹지 않으면서 이동하는 간선 (돈까스 먹은 상태)
import heapq
inf = 2000000007
V, E = map(int, input().split())
g = [[] for i in range(V+1)]
for i in range(E):
x, y, t, k = map(int, input().split())
g[x].append((y, t, k))
g[y].append((x, t, k))
def dijkstra(g, st):
dist = [inf for i in range(len(g))]
pq = []
dist[st] = 0
heapq.heappush(pq, (0, st))
while len(pq) > 0:
nowd, now = heapq.heappop(pq)
if dist[now] != nowd:
continue
for (nxt, l, _) in g[now]:
nxtd = nowd + l
if nxtd < dist[nxt]:
dist[nxt] = nxtd
heapq.heappush(pq, (nxtd, nxt))
return dist
dist = dijkstra(g, 1)
dist2 = [inf for i in range(V+1)]
for x in range(1, V+1):
for (y, t, k) in g[x]:
dist2[y] = min(dist2[y], dist[x] + t - k)
for x in range(1, V+1):
g[0].append((x, dist2[x], 0))
ans = dijkstra(g, 0)
print(*ans[2:], sep='\n')
같은 분 코드 : 다익스트라 2번 돌리는 경우 (파이썬 속도 1등)
다익스트라 한 번 돌리기 (dist 배열 생성):
먼저 1번 노드에서 시작해서 기본적인 최단 거리를 구합니다. 이를 통해 dist 배열을 얻습니다. dist[x]: 1번 노드에서 x번 노드까지 가는 최단 거리. dist2 배열 업데이트:
dist2 배열은 돈까스를 먹은 간선을 포함한 최단 경로를 구하는 배열입니다. dist2[y]: 1번 노드에서 y번 노드까지 가는 경로 중 돈까스를 먹으면서 가는 경로의 최단 거리. 이 배열은 간선이 실제로 사용되었는지 여부는 알 수 없습니다. 단순히 dist[x] + t - k로 x에서 y로 가는 간선에 돈까스를 먹으면서 이동했을 경우를 고려합니다. 가상의 더미 노드 0을 이용한 검증:
dist2 배열이 실제 존재하는 경로를 보장하지 않기 때문에, 더미 노드 0을 사용하여 경로가 진짜 간선인지 확인합니다. 더미 노드 0에서 다익스트라를 한 번 더 돌려서, 0번 노드를 통해서 이동하는 경로가 실제로 존재하는지 확인합니다. 이를 통해 0에서 바로 가는 경로와 0을 거쳐서 가는 경로 중 최소값을 선택할 수 있습니다. 결과:
0번 노드를 통해서 갱신된 dist2 배열을 기반으로, 1번 노드에서 y번 노드로 가는 최소 경로를 선택합니다. 이렇게 해서 돈까스를 먹은 경로와 먹지 않은 경로를 비교하여 최단 경로를 구할 수 있습니다. 결국, 0번 노드는 돈까스를 먹는 경로가 실제로 간선으로 존재하는지 확인하기 위해 사용되며, 이를 통해 최소 경로를 보장하는 과정입니다.
자바
import java.util.*;
import java.io.*;
public class Solution {
static int N,M;
static long INF=Long.MAX_VALUE;
static ArrayList<ArrayList<int[]>> G;
static long[][] V;
static PriorityQueue<Node> heap;
static class Node {
long t;
int x, state;
Node(long t, int x, int state) {
this.t = t;
this.x = x;
this.state = state;
}
}
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// init Graph
G = new ArrayList<ArrayList<int[]>>();
for (int i=0; i<N+1; i++) {
G.add(new ArrayList<>());
}
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int flavor = Integer.parseInt(st.nextToken());
G.get(a).add(new int[] {b,t,flavor});
G.get(b).add(new int[] {a,t,flavor});
}
// init V array
V = new long[2][N+1];
Arrays.fill(V[0],INF);
Arrays.fill(V[1],INF);
V[0][1] = 0;
// init heap
heap = new PriorityQueue<Node>(
(cur,next) -> Long.compare(cur.t,next.t));
heap.offer(new Node(0,1,0)); // t,x,state
while (!heap.isEmpty()) {
Node cur = heap.poll();
long t = cur.t;
int x = cur.x, state = cur.state;
if (t > V[state][x]) {
continue;
}
for (int[] next : G.get(x)) {
int nx = next[0];
long nt = t + next[1];
int flavor = next[2];
if (nt < V[state][nx]) {
heap.offer(new Node(nt,nx,state));
V[state][nx] = nt;
}
if (state == 0 && nt-flavor < V[1][nx]) {
heap.offer(new Node(nt-flavor,nx,1));
V[1][nx] = nt-flavor;
}
}
}
for (int i=2; i<N+1; i++) {
System.out.println(Math.min(V[0][i],V[1][i]));
}
}
}
댓글