백준 24425 タクシー 2 (Taxis 2)

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

24425번: タクシー 2 (Taxis 2)

 

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제 및 알아야 되는 정리

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

1753번: 최단경로

다익스트라 알고리즘을 사용하는 문제입니다. 다익스트라를 공부하고 오세요.

 

 

1. 핵심 아이디어

 

 먼저 일자로 된 지도부터 생각해봅시다. (빨간간선 파란간선은 빨강,파랑택시가 지니가는 통로를 의미)

 

일자 길에서 각 노드로 이동하기 위한 최소 비용은 다음과 같습니다.

 

 

필요 비용을 자세히 살펴보면 이제까지 이용한 파란 택시의 갯수 만큼 증가하는 것을 관찰 할 수 있습니다.

다음지역비용 = 현재지역비용 + 2^{(이제까지 이용한 파란 택시의 갯수)}

 

 

 

 

 

하지만 우리가 구해야되는 것은 일자직선에서의 경우가 아니라 그래프에서의 경우입니다.

해당 사실을 그래프로 적용할 필요가 있습니다.

 

그래프를 이용한 최단거리 탐색 알고리즘인 다익스트라를 사용할 것입니다.

Dist[현재노드][사용한 파란택시수]라고 정의하고

위에서 설명한 필요비용이 증가하는 사실을 이동시 비용이라고 정의한다면

 

다익스트라로 접근해서 문제를 쉽게 풀수 있습니다.

 

단, 파란 택시를 30번을 넘게이용하면 L를 초과하는것이 자명하므로
30번넘게 이용하는 경우는 고려하지 않습니다.

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

#define Debug(a,b) cout << a << " " << b << endl
#define Init(a,b) memset(a,b,sizeof(a))

const float INF = 1e15;
const int Dic[8][2] = { {0,1},{0,-1},{1,0},{-1,0} ,{1,1},{-1,-1},{1,-1},{-1,1} };

//////////////////////////////////////////////////////////////////////// 

int N, M, Q, L;
vector<pair<int, int>> V[200001];
int Dist[200001][31];

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    std::cin >> N >> M >> Q >> L;
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        V[a].emplace_back(b, c);
        V[b].emplace_back(a, c);
    }

    for (int i = 1; i <= N; i++)
        for(int j = 0; j <= 30; j++)
            Dist[i][j] = INF;

    priority_queue<pair<int, pair<int,int>>> pq;
    pq.push({ -1,{1,0} });
    Dist[1][0]= 1;

    while (pq.empty() == false)
    {
        pair<int, int> nowPos = pq.top().second;
        int nowValue = -pq.top().first;
        pq.pop();

        for (pair<int, int> nextP : V[nowPos.first])
        {
            int color = nextP.second; //택시 색상
            int nextBlueStack = color == 2 ? nowPos.second + 1 : nowPos.second; //이용한 파란택시 수
            pair<int, int> nextPos = { nextP.first ,nextBlueStack };
            int nextValue = nowValue + pow(2, nowPos.second); //다음 비용

            if (nextBlueStack > 30)
            {
            	//너무 크다.
                continue;
            }

            if (Dist[nextPos.first][nextBlueStack] > nextValue)
            {
                Dist[nextPos.first][nextBlueStack] = nextValue;
                pq.push({ -nextValue,nextPos });
            }
        }
    }

    for (int i = 0; i < Q; i++)
    {
        int a;
        std::cin >> a;
        int minValue = INF;
        
        //해당 노드로 이동하기 위한 가장 작은 비용을 찾는다.
        for (int j = 0; j <= 30; j++)
            minValue = min(minValue, Dist[a][j]);
        if (minValue > L)
            std::cout << "Large" << endl;
        else
            std::cout << minValue << endl;
    }

}