백준 16167번 A Great Way

문제 링크입니다: https://www.acmicpc.net/problem/16167

다익스트라 알고리즘 성격을 갖는 BFS(Breadth First Search) 알고리즘을 통해 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. c, d, e를 통해 a -> b로 가는 비용을 계산하고 단방향 그래프로 값을 입력합니다.

2. BFS 함수를 호출하여 중앙대(1번 거점)로부터 시작해서 갈 수 있는 거점을 최신화시킵니다.

i) 거리가 같을 경우, 지나쳐온 거점의 개수가 더 적을 경우 최신화 시킵니다.

ii) 기존 거리보다 짧을 경우 지나쳐온 거점의 개수와 상관없이 최신화 시킵니다.

3. 숭실대의 위치는 N번 거점이므로 2번을 수행한 뒤 result[N].first 즉, 1->N까지의 거리가 최신화가 되었는지 확인합니다.

i) 최신화가 되어있지 않고 무한대이면 갈 수가 없으므로 "It is not a great way."를 출력합니다.

ii) 최신화가 되어있다면 1->N으로 가는 경로가 존재하므로 최단거리와 지나쳐온 거점의 개수를 출력합니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

 

const int MAX = 100 + 1;

const int INF = 987654321;

 

int N, M;

vector<pair<int, int>> graph[MAX];

pair<int, int> result[MAX]; //distance, # of vertex

 

void BFS(void)

{

        queue<int> q;

        q.push(1); //중앙대

        result[1].first = 0;

        result[1].second = 1;

 

        while (!q.empty())

        {

                 int cur = q.front();

                 q.pop();

 

                 for (int i = 0; i < graph[cur].size(); i++)

                 {

                         int neighbor = graph[cur][i].first;

                         int neighborDist = graph[cur][i].second;

                        

                         //거리는 같은데

                         if (result[neighbor].first == (result[cur].first + neighborDist))

                         {

                                 //지나가는 정점이 더 적은 경우

                                 if (result[neighbor].second > result[cur].second + 1)

                                 {

                                          result[neighbor].second = result[cur].second + 1;

                                          q.push(neighbor);

                                 }

                         }

 

                         //거리가 더 짧을 경우

                         if (result[neighbor].first > result[cur].first + neighborDist)

                         {

                                 result[neighbor].first = result[cur].first + neighborDist;

                                 result[neighbor].second = result[cur].second + 1;

                                 q.push(neighbor);

                         }

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int a, b, c, d, e;

                 cin >> a >> b >> c >> d >> e;

 

                 //추가 요금이 붙는 경우

                 if (e > 10)

                         c += ((e - 10)*d);

                 graph[a].push_back({ b,c });

        }

       

        //초기화

        for (int i = 0; i <= N; i++)

        {

                 result[i].first = INF;

                 result[i].second = INF;

        }

        BFS();

 

        if (result[N].first == INF)

                 cout << "It is not a great way.\n";

        else

                 cout << result[N].first << " " << result[N].second << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~