https://www.acmicpc.net/problem/2211
2211번: 네트워크 복구
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.
www.acmicpc.net
MST로 구하면 될줄 알았는데...
다름 조건 때문에 단순 MST로는 구할수 없다.
|
다익스트라를 변형해서, 1번부터 K번까지의 최단거리를 구하는 문제로 변경함.
다익스트라 변경은 머리에 잘 안들어옮. ㅠㅠ
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class BOJ2211 {
static int N, M;
static ArrayList<Edge>[] edges;
static int[] D;
static class Edge implements Comparable<Edge> {
int s,e, v;
Edge(int s, int e, int v){
this.s = s;
this.e = e;
this.v = v;
}
@Override
public int compareTo(Edge o) {
return this.v - o.v;
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_boj2211.txt"));
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());
edges = new ArrayList[N+1];
D = new int[N+1];
for (int i = 1; i <=N ; i++) edges[i] = new ArrayList<>();
int a, b, c;
for (int i = 0; i < M ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
edges[a].add(new Edge(a, b,c));
edges[b].add(new Edge(b, a,c));
}
Arrays.fill(D, Integer.MAX_VALUE);
PriorityQueue<Edge> pq = new PriorityQueue<>();
Edge ed = new Edge(0,1,0);
pq.add(ed);
ArrayList<Edge> res = new ArrayList<>();
while (!pq.isEmpty()){
ed = pq.poll();
if(D[ed.e]!=Integer.MAX_VALUE) continue;
D[ed.e] = ed.v;
if(ed.s != 0) {
res.add(ed);
}
for (Edge nd:edges[ed.e]) {
if(D[nd.e]!=Integer.MAX_VALUE) continue;
//D[nd.e] = D[ed.e] + nd.v;
pq.add(new Edge(ed.e, nd.e, ed.v+nd.v));
}
}
System.out.println(res.size());
for (Edge r: res) {
System.out.println(r.s+" "+r.e);
}
}
}