[白俊]9370号未確認目的地/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
25.最短経路
図形の幹線に重みがない場合は、BFSを使用して最短距離を検索できます.重みがあればどうなりますか?
Java/Python
3.目的地が確認されていない
9370号
最短距離アルゴリズム応用問題
始点→目的地までの最短距離で特定の幹線を通過する場合の簡単なまとめです.
「Dijkstraアルゴリズム」(Dijkstra Algorithm)を使用します.
import java.io.*;
import java.util.*;
class Node implements Comparable<Node>{
int end, weight;
public Node(int end, int weight){
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
public class Main {
static final int INF = 10_000_000;
static int V, E, T;
static int start, g, h;
static int[][] graph;
static int[] dist;
static boolean[] check;
static List<Integer> resultList;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int testcase = Integer.parseInt(br.readLine());
for(int i = 0; i < testcase; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
// 그래프 배열 선언
graph = new int[V + 1][V + 1];
dist = new int[V + 1];
for(int j = 0; j < graph.length; j++)
Arrays.fill(graph[j], INF);
Arrays.fill(dist, INF);
check = new boolean[V + 1];
// s, g, h 초기화
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
// 그래프 정보 저장
for(int j = 0; j < E; j++){
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
graph[v1][v2] = graph[v2][v1] = distance * 2;
}
graph[h][g] = graph[g][h] = graph[h][g] - 1;
resultList = new ArrayList<>();
for(int j = 0; j < T; j++)
resultList.add(Integer.parseInt(br.readLine()));
dijkstra();
Collections.sort(resultList);
for(int num : resultList)
if(dist[num] % 2 == 1) bw.write(num + " ");
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
public static void dijkstra() {
PriorityQueue<Node> pqueue = new PriorityQueue<>();
pqueue.offer(new Node(start, 0));
dist[start] = 0;
while (!pqueue.isEmpty()) {
Node now = pqueue.poll();
int cur = now.end;
if(!check[cur]){
check[cur] = true;
for (int i = 1; i <= V; i++) {
if(!check[i] && dist[i] > dist[cur] + graph[cur][i]){
dist[i] = dist[cur] + graph[cur][i];
pqueue.offer(new Node(i, dist[i]));
}
}
}
}
}
}
from heapq import heappush, heappop
import sys
# dijkstra 경로 탐색
def dijkstra(start):
dp = [100000000 for i in range(n + 1)]
dp[start] = 0
heap = []
heappush(heap, [0, start])
while heap:
we, nu = heappop(heap)
for ne, nw in graph[nu]:
wei = we + nw
if dp[ne] > wei:
dp[ne] = wei
heappush(heap, [wei, ne])
return dp
testcase = int(sys.stdin.readline())
for _ in range(testcase):
n, m, t = map(int, sys.stdin.readline().split())
start, g, h = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
dist = []
for j in range(m):
a, b, d = map(int, sys.stdin.readline().split())
graph[a].append([b, d])
graph[b].append([a, d])
for k in range(t):
dist.append(int(sys.stdin.readline()))
start_ = dijkstra(start)
g_ = dijkstra(g)
h_ = dijkstra(h)
resultlist = []
for l in dist:
if start_[g] + g_[h] + h_[l] == start_[l] or start_[h] + h_[g] + g_[l] == start_[l]:
resultlist.append(l)
resultlist.sort()
for f in resultlist:
print(f, end=' ')
print()
Reference
この問題について([白俊]9370号未確認目的地/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-9370번-미확인-도착지-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol