1. 풀이 어떤 node의 k번째 최단경로는 아래의 다익스트라구조에서 [구역1]에 해당하는부분에 k번째로 방문됐을때에 해당된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1.풀이 거쳐가는 노드수의 최솟값을 계산해야한다. 하이퍼튜브는 k가지 노드를 모두 연결해주는, 즉 1의 가중치를 가지게 해주는 장치이다. 따라서 아래와 같이 가중치를 주면 하이퍼튜브를 통해서 노드를 연결해주는 그래프를 만들 수 있다. 노드 -> 하이프튜브 : 가중치 1 하이퍼튜브 -> 노드 : 가중치 0​ 이렇게 하면 (노드a->하이퍼튜브->노드b) 의 cost가 1이 되어서 다익스트라 처럼 풀 수 있다. ​ 2.소스코드 import heapq maxNum=9876543210 N,K,M=map(int,input().split()) graph={} for i in range(1,N+M+1): graph[i]=[] for i in range(M): temp=list(map(int,input().split()..

1. 풀이 가중치 있는 그래프이므로 일반적인 다익스트라 알고리즘을 사용하면 되는데, 특정 경로를 지났는지를 확인해주어야 한다. 다익스트라는 아래와 같이 구성된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1. 최단거리 2. 최소스패닝 트리(MST)

1. 풀이 (1) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0 (2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다. (bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.) (3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다 즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수 ​ 2. 소스코드 import heapq ..

어떤노드에 처음으로 방문한 순간이 최단거리임이 보장된다(bfs와 비슷). 따라서 주어진 끝노드에 도달하면 해당 비용을 출력한 후 종료한다. import heapq N=int(input()) M=int(input()) graph={} for i in range(N): graph[i+1]=[] for i in range(M): a,b,c=map(int,input().split()) graph[a].append([b,c]) start,end=map(int,input().split()) maxNum=9876543210 nodeDist=[maxNum for i in range(N+1)] dij=[[0,start]] heapq.heapify(dij) while(dij): temp=heapq.heappop(dij) ..

1. 풀이 1) 다음의 두가지 거리가 필요하다. (파티장 x에서 a까지의 최단거리) + (a에서 파티장x까지 최단거리) 2) (파티장 x에서 a까지의 최단거리) : X를 시작점으로 다익스트라를 이용해서 구한다 3) (a에서 파티장x까지 최단거리) : edge를 모두 반대방향으로 바꾼 후(cost는 그대로) 다익스트라. 위가 성립하는 이유는 (graph에서 a->b 까지의 최단거리) == (edge의 방향을 바꾼 graph에서 b->a까지의 최단거리) 이기 때문에 자명하다. 2. 소스코드 import heapq #input N,M,X=map(int,input().split()) graph={} graphR={} for i in range(1,N+1): graph[i]=[] graphR[i]=[] for i..

*다익스트라의 정석 문제 #include #include #include #include #include #define INF 987654321 #define max_v 20001 #define max_e 300001 using namespace std; int V, E; // graph[i]={j,w} : i 에서 j노드로 가는 가중치 w vector graph[max_v]; int dist[max_v]; // distance[j] : 출발노드에서 j노드까지의 거리, 초기엔 모두 INF void dijst(int start) { for (int i = 1; i w) { dist[toNode] = w; pq.push({ w, toNode }); } } } return; } int main() { cin...