KCM Travel


작성일 : 2017-01-18 22:13:56
조회수 : 559



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


일반적인 다익스트라는 가중치가 1개가 있어 이 가중치가 가장 적은 값을 가질 때 최단 경로로 정의합니다. 하지만 여기서는, 일반적인 가중치에 <돈, 시간> 의 2가지 가중치가 추가되어 있습니다. 더 빠르게 도착할 수 있더라도 돈이 $M$원을 넘어서면 갈 수 없는 경로이므로 이러한 부분을 고려하여 최단경로를 구했습니다.


풀고 보니 별로 좋은 방법은 아닌 것 같지만.. 제한시간이 10초이고 도시의 수가 100개, 최대 비용이 10000 이므로 이를 배열로 만들어 현재 위치를 어느 비용에 도착했는지를 저장한 후, 모든 경로를 탐색 후 $M$원 이하의 비용을 모두 검사하여 가장 작은 시간을 검색했습니다. 이렇게 푸니 약 2.5초.. 하지만 이렇게 안하고 다익스트라를 좀 더 잘 짜면 굉장히 빠른 속도로 풀 수 있을 것입니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#define MAX 10001
using namespace std;

class Node
{
public:
    int next, money, time;
    Node(int a, int b,int c) { next = a, money=b, time = c; }

    bool operator <(const Node &n) const
    {
        return time == n.time ? money > n.money : time > n.time;
    }
};

int dp[111][11111];

int main()
{
    int testCase;

    cin >> testCase;

    for (int cases = 0; cases < testCase; cases++)
    {
        int n, m, k;
        bool visit[101] = { 0 };
        priority_queue<Node> pq;
        vector<vector <Node> > V;

        cin >> n >> m >> k;
        V.resize(n + 1);

        for (int i = 0; i < k; i++)
        {
            int u, v, x, d;

            cin >> u >> v >> x >> d;

            V[u].push_back(Node(v, x, d));
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = 2e9;

        dp[1][1] = 0;
        
        pq.push(Node(1, 0, 0));

        while (!pq.empty())
        {
            Node temp = pq.top();
            pq.pop();

            int cur = temp.next, cmoney = temp.money, ctime = temp.time;

            if (dp[cur][cmoney] < ctime) continue;
            dp[cur][cmoney] = ctime;

            int len = V[cur].size();

            for (int i = 0; i < len; i++)
            {
                int next = V[cur][i].next, nmoney = V[cur][i].money, ntime = V[cur][i].time;

                if (cmoney + V[cur][i].money <= m && dp[next][cmoney+nmoney] > ctime+ntime)
                {
                    dp[next][cmoney + nmoney] = ctime + ntime;
                    pq.push(Node(next, cmoney + V[cur][i].money, dp[next][cmoney + nmoney]));
                }
            }
        }

        int ans = 2e9;

        for (int i = 1; i <= m; i++)
            if (ans > dp[n][i]) ans = dp[n][i];

        if (ans == 2e9) cout << "Poor KCM\n";
        else cout << ans << "\n";

        memset(dp, 0, sizeof(dp));
    }
}

KCM Travel - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글