백준 6951번 Packet Routing c++ 풀이

문제

The date is October 29th, 1969. Today, scientists at UCLA made history by exchanging data between two computers over a network. The transmission wasn't very spectacular: only the first two letters of the word login were received before the system crashed. Nevertheless, the researchers are beginning to design larger computer networks and they need your help.

A computer network is a collection of N (2≤N≤100) computers and W wires. The computers are identified by the numbers 1,2,…,N Each wire connects exactly two computers, allowing packets of data to flow in both directions between the computers. The wires are placed so that it is possible to send packets (directly or indirectly by passing through other computers) between every pair of computers. In fact, the placement of the wires has been optimized so that there is exactly one path between every pair of computers. If the packet travels along several wires to get from the source computer to the destination computer, the time needed for the packet to travel along this path is the sum of the times required for the packet to travel along each individual wire. You are to write a program that computes the amount of time needed for a packet to travel between a given pair of distinct computers.

입력

The first line of the input file contains the three positive integers N, W, P

For each wire, a line follows giving the identification numbers of the two computers connected by the wire, and an integer between 1 and 500 giving the time required for a packet to travel along this wire.

 P(1≤P≤10000) is the number of packets which need to be sent. For each packet, a line follows giving the identification numbers of the packet's source and destination computers.

출력

For each packet, find the route through the network which will allow the packet to travel from the source computer to the destination computer. Output the travel time of this route on a single line.

예제 입력 1 복사

3 2 3
1 2 100
2 3 150
2 1
2 3
1 3

예제 출력 1 복사

100
150
250

 

 

기본 플로이드 워셜

 

#include <bits/stdc++.h>

using namespace std;
const int INF = 987654321;
int network[101][101];
int n, w, p;

void floyd() {

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (network[i][j] > network[i][k] + network[k][j]) {
                    network[i][j] = network[i][k] + network[k][j];
                }
            }
        }
    }

}

int main() {

    cin >> n >> w >> p;


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            network[i][j] = INF;
            if (i == j) {
                network[i][j] = 0;
            }
        }
    }

    for (int i = 0; i < w; i++) {
        int from, to, cost;
        cin >> from >> to >> cost;
        network[from][to] = cost;
        network[to][from] = cost;
    }

    floyd();

    for (int i = 0; i < p; i++) {
        int from, to;
        cin >> from >> to;
        cout << network[from][to] << "\n";
    }


}