백준 18223번 - 민준이와 마산 그리고 건우

https://www.acmicpc.net/problem/18223

18223번: 민준이와 마산 그리고 건우

 

해당 문제는 다익스트라 알고리즘을 사용하여 해결하는 문제이다.

 

일단 문제는 아래와 같이 두 분류로 나눌 수 있다.

 

1. 첫째 노드로 시작해서 V번째 노드로 끝나는 최단거리 D1

2. 첫째노드로 시작해서 P 노드를 지나서 V 번째 노드에 도착하는 최단거리 D2

 

그런데 여기서 D2 의 경로는 두개의 경로로 나눌 수 있다.

 

D2_1 = 첫째노드로 시작해서 P노드까지 가는 최단거리

D2_2 = P노드로 시작해서 마지막 노드까지 가는 최단거리

 

D2 = D2_1 + D2_2 와 같은 수식이 나오게 된다.

 

 

즉 D1 < D2 (= D2_1 + D2_2) 이면 "GOOD BYE"를 출력하면 되고,

 

D1 >= D2 (= D2_1 + D2_2) 이면 "SAVE HIM" 을 출력하면 된다.

 

 

 

1. C++

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

int V,E,P;
vector < pair<int,int> > map[5002];
int INF = INT_MAX;
int min_roots[5002];

int dijkstra(int stp,int endp) {
    
    for (int i = 0; i <= V; i++) {
        min_roots[i] = INF;
    }
    
    priority_queue< pair<int,int> > pq;
    pq.push(make_pair(0,stp));
    min_roots[stp] = 0;
    
    while(!pq.empty()) {
        int cur_v = pq.top().second;
        int cur_d = -pq.top().first;

        pq.pop();
        
        if (min_roots[cur_v] < cur_d) continue;
        
        for (int i = 0; i < map[cur_v].size(); i++) {
            int next_v = map[cur_v][i].first;
            int next_d = map[cur_v][i].second + cur_d;
    
            if (min_roots[next_v] > next_d) {
                min_roots[next_v] = next_d;
                pq.push(make_pair(-next_d,next_v));
            }
        }
    }
    
    return min_roots[endp];
}

int main()
{
    
    cin >> V >> E >> P;
    
    for (int i = 0; i < E; i++) {
        int u,v,d;
        
        cin >> u >> v >> d;
        
        map[u].push_back(make_pair(v,d));
        map[v].push_back(make_pair(u,d));
    }
    
    int min_root = dijkstra(1,V);
    int f_root = dijkstra(1,P) + dijkstra(P,V);
    
    if (min_root < f_root) cout << "GOOD BYE";
    else cout << "SAVE HIM";
    
    
    return 0;
}

 

 

2. JAVA

import java.io.*;
import java.util.*;

public class Main
{   
    static int V,E,P;
    static int INF = Integer.MAX_VALUE;
    static ArrayList<Node>[] map;
    static int[] resultArr;
    
    static class Node implements Comparable<Node> {
        int u,d;
        
        public Node(int u, int d) {
            this.u = u;
            this.d = d;
        }
        
        @Override
        public int compareTo(Node o) {
            if (this.d < o.d) {
                return -1;
            }
            return 1;
        }
    }
    
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer stk = new StringTokenizer(br.readLine()," ");
		V = Integer.parseInt(stk.nextToken());
		E = Integer.parseInt(stk.nextToken());
		P = Integer.parseInt(stk.nextToken());
	
	    map = new ArrayList[V+1];
	    resultArr = new int[V+1];
	    
	    for (int i = 0; i <= V; i++) {
	        map[i] = new ArrayList<Node>();
	    }
	    
	    for (int i = 0; i < E; i++) {
	        stk = new StringTokenizer(br.readLine()," ");
	        
	        int u = Integer.parseInt(stk.nextToken());
	        int v = Integer.parseInt(stk.nextToken());
	        int d = Integer.parseInt(stk.nextToken());
	        
	        map[u].add(new Node(v,d));
	        map[v].add(new Node(u,d));
	    }
	    
	    int minDist1 = dijkstra(1,V);
	    int minDist2 = dijkstra(1,P) + dijkstra(P,V); 
	    String answer;
	    
	    if (minDist1 < minDist2) answer = "GOOD BYE";
	    else answer = "SAVE HIM";
	    
	    bw.write(answer + "");
	    bw.close();
	    br.close();
	}
	
	static int dijkstra(int startP, int endP) {
	    
	    Arrays.fill(resultArr,INF);

	    PriorityQueue<Node> pq = new PriorityQueue<>();
	    pq.offer(new Node(startP,0));
	    resultArr[startP] = 0;
	    
	    while(!pq.isEmpty()) {
	        int cur_u = pq.peek().u;
	        int cur_d = pq.peek().d;
	        
	        pq.poll();
	        
	        if (resultArr[cur_u] < cur_d) continue;
	        
	        for (int i = 0; i < map[cur_u].size(); i++) {
	            int next_u = map[cur_u].get(i).u;
	            int next_d = map[cur_u].get(i).d + cur_d;
	            
	            if (resultArr[next_u] > next_d) {
	                resultArr[next_u] = next_d;
	                pq.offer(new Node(next_u,next_d));
	            }
	        }
	    }
 	    
	    return resultArr[endP];
	}
}