※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
일반적인 다익스트라는 가중치가 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));
}
}