[해커랭크] Floyd : City of Blinding Lights (C++)

문제 링크: www.hackerrank.com/challenges/floyd-city-of-blinding-lights/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

Floyd : City of Blinding Lights | HackerRank

1. 주의할 점

- 모든 점<->점에 대한 정보 : 플로이드 와샬 알고리즘에 대해 알고있어야 한다

- 시작점과 끝점이 같은 간선이 여러개 입력될 경우, 가장 마지막에 입력된 가중치를 저장한다(본문 참조)

 

2. 구현

- 간선에 대한 정보를 담는 Arr[][] 배열을 초기화해준다(자기자신으로 향할 경우 0, 이외의 경우 MAX)

- 간선에 대한 정보를 입력받아서 Arr[][] 배열에 할당한다

- Floyd() 함수를 통해 Arr[][] 배열의 값들을 재설정한다

- Query를 통해 최단경로의 값어치를 출력하되, Arr[][]의 값이 MAX라면 경로가 없다는 의미로, -1을 출력

 

#define MAX 987654321
#include <bits/stdc++.h>
using namespace std;

vector<string> split_string(string);
int arr[401][401];
int node;

void floyd(int node){
    for(int k=1;k<=node;k++)
        for(int i=1;i<=node;i++)
            for(int j=1;j<=node;j++)
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];             
}


int main()
{
    int road_nodes;
    int road_edges;
    
    for(int i=1;i<=400;i++)
        for(int j=1;j<=400;j++){
            if(i==j) arr[i][j]=0;
            else arr[i][j]=MAX;
        }
            
    cin >> road_nodes >> road_edges;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int a,b,val;

    for (int i = 0; i < road_edges; i++) {
        cin>>a>>b>>val;
        arr[a][b]=val;      
    }
    floyd(road_nodes);
    
    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string xy_temp;
        getline(cin, xy_temp);

        vector<string> xy = split_string(xy_temp);

        int x = stoi(xy[0]);

        int y = stoi(xy[1]);
        arr[x][y]==MAX ? cout<< -1 : cout<<arr[x][y];
        cout<<'\n';
    }   
    return 0;
}