백준 - Packet Routing 6951 java

---

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

6951번: Packet Routing

---

[문제 해설]

• 해당 문제는 패킷 라우팅에 관한 설명입니다.
• 패킷에서 패킷까지의 이동 거리가 주어지고 입력으로 들어오는 패킷의 이동 거리의 최소값을 출력하는 문제입니다.
• 벨만포드, 플로이드-워셜 알고리즘을 통해 해당 문제를 해결 할 수 있을거 같습니다.

---

저는 플로이드-워셜 최단경로 알고리즘을 이용해 문제를 해결했습니다.

 

[Java]

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

public class Main {

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());

        int map[][] = new int[n+1][n+1];

        for(int i=0; i<=n; i++) {
            for(int j=0; j<=n; j++){
                if(i==j) map[i][j] = 0;
                else map[i][j] = 10000001;
            }
        }

        for(int i=0; i<w; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[a][b] = Math.min(cost, map[a][b]);
            map[b][a]  = Math.min(cost, map[b][a]);
        }

        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++)
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
            }
        }

        for(int i=1; i<=p; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            bw.write(map[start][end] + "\n");
        }

        bw.close();
    }

}