BOJ 10217 - KCM Travel

時間制限メモリ制限解答を提出正解正解正解正解率10秒256 MB 9832202298517.302%
質問する
努力の末、燦民はついに2014年のGoogle Code Jam World Finalsに入った.グーグルからの招待状をもらって嬉しかったのは、よく読んだミンも重要な事実に気づいたことだ.最近の勢いのおかげで、グーグルも大企業のように費用削減に熱中している.
招待状の内容によると、グーグルは賛民に最大M元の旅行費用を支払う.仁川(インチョン)でLAへの直行便を1回中断するのはそんなに難しいのかという質問だが、これからの決勝戦を考えると、大会の外に気を使いたくないのも事実だ.このため、賛民は仁川(インチョン)からLAまでのMウォン以下で最も早く行ける道を2番目に選ぶことにした.
各空港間で運賃と移動時間を提供する際、仁川からLAまでの最速路線を見つけ、チャンミンの大会参加を支援する.
入力
入力ファイルの最初の行には、テストケース数を表す自然数Tが与えられる.そしてT個のテストケースです.
各試験例の第1行において、空港の数N(2≦N≦100)、総サポート費用M(0≦M≦10000)、チケット情報の数K(0≦K≦10000)が空白に分割される.次に、K行において、チケット毎の出発空港u、到着空港v(1≦u,v≦N,u≠v)、料金c(1≦c≦M,整数)、および所要時間d(1≦d≦1000)を空白に分割する.仁川は永遠に1番都市で、ロサンゼルスは永遠にN番都市です
しゅつりょく
各テストボックスの1行には、賛民がLAに到着するのに要する最短時間が印刷されます.
LAに到着できない場合は「Poor KCM」を出力します.
に近づく
これは一般的な多益アルゴリズムにおいて,コストと時間のDP感覚が増大するという問題である.
dist[N][M]のテーブルを作成して実装を開始した.
コメントをうまく処理すれば簡単に解決できる問題です.
に答える
優先キューに格納し、演算子()で処理する構造体ノードが作成されました.
最短時間のノードを抜く限り、挿入時にMを超えないでください.
挿入中に<=を<と書いて10分以上飛びました.ミスを減らそう

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

struct Node
{
	int v, c, d;
	Node(int vv, int cc, int dd) : v(vv), c(cc), d(dd) {}
};

struct compare
{
	bool operator()(Node A, Node B)
	{
		return A.d > B.d;
	}
};

int T, N, M, K, u, v, c, d;
int dist[101][10001]; // i까지 j원으로 도착할때 최소시간
vector<Node> edge[101];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN(T);
	while (T--)
	{
		CIN3(N, M, K);
		FUP(i, 1, N)
		{
			edge[i].clear();
			FUP(j, 0, M)
			{
				dist[i][j] = INT_MAX;
			}
		}
		while (K--)
		{
			CIN2(u, v);
			CIN2(c, d);
			edge[u].push_back(Node(v, c, d));
		}

		priority_queue<Node, vector<Node>, compare> pq;
		dist[1][0] = 0;
		pq.push(Node(1, 0, 0));
		string answer = "Poor KCM";
		while (!pq.empty())
		{
			Node node = pq.top();
			if (node.v == N)
			{
				answer = to_string(node.d);
				break;
			}
			pq.pop();
			if (dist[node.v][node.c] < node.d) continue;
			for (Node next : edge[node.v])
			{
				if (node.c + next.c > M || dist[next.v][node.c + next.c] <= node.d + next.d) continue;
				dist[next.v][node.c + next.c] = node.d + next.d;
				pq.push(Node(next.v, node.c + next.c, node.d + next.d));
			}
		}
		COUT(answer);
		ENDL;
	}

	return 0;
}