문제 링크
조건
- N : 학생 수, 1~1000 이하
- M : 단방향 도로 정보, 1~10,000 이하
- X : 파티를 여는 학생 번호
접근 방법
- Floyd-Warshall(플로이드 워셜)
- O(N3) 시간복잡도(오래걸림)
- 모든 노드에서 각각의 노드로 이동할 때 모든 최단거리를 구함
- Dijkstra
- 단방향 값어치 정보가 주어진다 => dijkstra를 두 번 진행
- X번 학생 집으로 들어오는 방향에 대한 dijkstra (각 친구들이 파티에 올 때 걸리는 최단시간)
- X번 학생 집에서 나가는 방향에 대한 dijkstra (각 친구들이 집으로 돌아갈 때 걸리는최단시간)
솔루션
- Floyd-Warshall => 31152KB, 1884ms
public class Main {//floyd-warshall
static int N,M,X;//마을 수, 인접지역 cost 개수, 파티하는 마을
static int[][] adj;
static final int MAX = Integer.MAX_VALUE >> 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
adj = new int[N+1][N+1];//마을번호 1~N
for(int i = 1; i < N+1; i++) {
for(int j = 1; j < N+1; j++) {
adj[i][j] = MAX;
}
adj[i][i] = 0;//자기가 살고있는 마을까지는 0
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
if(d < adj[s][e]) adj[s][e] = d;
}
//플로이드워샬
for(int k = 1; k < N+1; k++) {
for(int i = 1; i < N+1; i++) {
for(int j = 1; j < N+1; j++) {
if(adj[i][j] > adj[i][k]+adj[k][j]) {//k번째 거쳐서 가는게 더 빠르다면
adj[i][j] = adj[i][k]+adj[k][j];
}
}
}
}
int ans = 0;
for(int i = 1; i < N+1; i++) {//갔다가 돌아오는 거리
ans = Math.max(ans, adj[i][X]+adj[X][i]);
}
System.out.println(ans);
}
}
- Dijkstra => 22880KB, 352ms
public class Main {//Dijkstra with no PriorityQueue
static int N,M,X;//마을 수, 인접지역 cost 개수, 파티하는 마을
static int[][] adj;
static final int MAX = Integer.MAX_VALUE >> 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
adj = new int[N+1][N+1];//마을번호 1~N
for(int i = 0; i < N+1; i++) {
Arrays.fill(adj[i], MAX);
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
adj[s][e] = d;
}
int[] come = new int[N+1];
int[] back = new int[N+1];
Arrays.fill(come, MAX);
Arrays.fill(back, MAX);
for(int i = 1; i < N+1; i++) {
if(adj[i][X] < come[i]) come[i] = adj[i][X];
if(adj[X][i] < back[i]) back[i] = adj[X][i];
}
//파티장으로 갈때
boolean[] check = new boolean[N+1];
check[X] = true;
while(true) {
int idx = -1;
int min = MAX;
for(int i = 1; i < N+1; i++) {
if(check[i]) continue;//이미 방문함
if(come[i] < min) {
min = come[i];
idx = i;
}
}
if(idx == -1) break;
check[idx] = true;
for(int i = 1; i < N+1; i++) {
if(adj[i][idx] == MAX) continue;//인접X
if(come[i] > adj[i][idx] + come[idx]) {//idx거쳐서 가는게 더 빠르다면
come[i] = adj[i][idx] + come[idx];
}
}
}
//파티장에서 돌아올 때
check = new boolean[N+1];
check[X] = true;
while(true) {
int idx = -1;
int min = MAX;
for(int i = 1; i < N+1; i++) {
if(check[i]) continue;//이미 방문함
if(back[i] < min) {
min = back[i];
idx = i;
}
}
if(idx == -1) break;
check[idx] = true;
for(int i = 1; i < N+1; i++) {
if(adj[idx][i] == MAX) continue;//인접X
if(back[i] > adj[idx][i] + back[idx]) {//idx거쳐서 가는게 더 빠르다면
back[i] = adj[idx][i] + back[idx];
}
}
}
int ans = 0;
for(int i = 1; i < N+1; i++) {//갔다가 돌아오는 거리
if(i == X) continue;
ans = Math.max(ans, come[i] + back[i]);
}
System.out.println(ans);
}
}
- Dijkstra (우선순위 큐 사용) => 18908KB, 216ms
public class Main {//Dijkstra with PriorityQueue
static int N,M,X;//마을 수, 인접지역 cost 개수, 파티하는 마을
static List[] adj, radj;
static final int MAX = Integer.MAX_VALUE >> 1;
static int[] come, back;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
adj = new ArrayList[N+1];
radj = new ArrayList[N+1];
for(int i = 1; i < N+1; i++) {
adj[i] = new ArrayList<int[]>();
radj[i] = new ArrayList<int[]>();
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
adj[s].add(new int[] {e,d});
radj[e].add(new int[] {s,d});
}
come = new int[N+1];
back = new int[N+1];
Arrays.fill(come, MAX);
Arrays.fill(back, MAX);
dikstra(X, adj, come);
dikstra(X, radj, back);
System.out.println(Arrays.toString(come));
System.out.println(Arrays.toString(back));
int ans = 0;
for(int i = 1; i < N+1; i++) {//갔다가 돌아오는 거리
if(i == X) continue;
ans = Math.max(ans, come[i] + back[i]);
}
System.out.println(ans);
}
private static void dikstra(int x, List[] adj, int[] dik) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] n1, int[] n2) {
return Integer.compare(n1[1], n2[1]);
}
});
boolean[] check = new boolean[N+1];
pq.add(new int[] {x,0});
while(!pq.isEmpty()) {
int[] cur = pq.poll();
int curNode = cur[0];
int curDis = cur[1];
check[curNode] = true;
for(int[] info : (List<int[]>) adj[curNode]) {//인접노드 for문
int n = info[0];
int d = info[1];
if(dik[n] > d + curDis) {
dik[n] = d + curDis;
pq.offer(new int[] {n,dik[n]});
}
}
}
}
}
리뷰
- 플로이드워셜은 시간초과 나야 정상인듯,,
- 단방향 간선 정보가 주어졌을 때, 이 문제처럼 들어오는 방향과 나가는 방향에 대해 각각 dijkstra를 두 번만 구해서 전체 최소값을 구할 수 있음!