[SWEA 5684] [Professional] 운동 (C++,JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRxnnah2sDFAUo

SW Expert Academy

1. 주의할 점

- 노드의 개수 <= 400, 단방향 그래

- BFS, 다익스트라, Travel Salesman Problem 등등 여러가지 생각해봤지만 우선순위 큐(Heap)을 이용한 다익스트라로 구현하면 가능하다고 판단

 

2. 구현

- 우선순위큐를 이용한 다익스트라로 구현

- 각 노드마다 모두 한번씩 돌려봤다

 

<C++ 코드>

#define MAX 987654321
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int idx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;

int main() {
	int test, node, edge, start, end, vv;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> node >> edge;
		vector<info> v[401];
		int dist[401];
		for (int i = 0; i < edge; i++) {
			cin >> start >> end >> vv;
			tmp.idx = end;
			tmp.val = vv;
			v[start].push_back(tmp);
		}
		int result = MAX;
		for (int i = 1; i <= node; i++) {
			for (int j = 1; j <= node; j++)
				dist[j] = MAX;
			priority_queue<info,vector<info>,cmp> pq;
			tmp.idx = i;
			tmp.val = 0;
			pq.push(tmp);
			while (!pq.empty()) {
				int cidx = pq.top().idx;
				int cv = pq.top().val;
				pq.pop();
				if (cv > result) continue;
				for (int j = 0; j < v[cidx].size(); j++) {
					int next = v[cidx][j].idx;
					int nv = v[cidx][j].val;
					if (dist[next] > cv + nv) {
						dist[next] = cv + nv;
						tmp.idx = next;
						tmp.val = cv + nv;
						pq.push(tmp);
					}
				}
			}
			result = min(result, dist[i]);
		}
		cout << "#" << t << " " << result << '\n';
	}
	system("pause");
	return 0;
}

 

<JAVA 코드>

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Solution_d4_5684_운동 {
	static class Info implements Comparable<Info>{
		int idx,val;
		public Info(int idx, int val) {		
			this.idx = idx;
			this.val = val;
		}
		@Override
		public int compareTo(Info o) {		
			return Integer.compare(this.val, o.val);
		}			
	}
	static Queue<Info> q;
	static int node,edge;
	static List<Info> li[];
	static int dist[];
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for(int t=1;t<=test;t++) {
			node = sc.nextInt();
			edge = sc.nextInt();
			//초기화
			li = new ArrayList[node+1];
			for(int i=1;i<=node;i++)
				li[i] = new ArrayList<>();
			for(int i=0;i<edge;i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				int val = sc.nextInt();
				li[start].add(new Info(end,val));
			}
			int result = Integer.MAX_VALUE;
			for(int i=1;i<=node;i++) {
				dist=new int[node+1];
				q = new LinkedList<Info>();
				for(int j=1;j<=node;j++)
					dist[j]=Integer.MAX_VALUE;
				q.add(new Info(i,0));
				Info ii;
				while(!q.isEmpty()) {
					ii = q.poll();
					int cidx = ii.idx;
					int cv = ii.val;
					if(cv>result) continue;
					for(int j=0;j<li[cidx].size();j++) {
						int next = li[cidx].get(j).idx;
						int nv = li[cidx].get(j).val;
						if(dist[next]> cv + nv) {
							dist[next]=cv+nv;
							q.add(new Info(next,dist[next]));
						}
					}
				}
				result = Math.min(dist[i], result);				
			}
			if(result==Integer.MAX_VALUE) result=-1;
			System.out.println("#"+t+" "+result);
		}
	}
}