結果

問題 No.1 道のショートカット
ユーザー pocarist
提出日時 2015-07-14 13:15:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,143 bytes
コンパイル時間 941 ms
コンパイル使用メモリ 97,664 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 04:09:21
合計ジャッジ時間 2,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <complex>
#include <cassert>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max()/2;

//http://www.prefield.com/algorithm/graph/dijkstra.html
typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Weight weight2;
	Edge(int src, int dst, Weight weight, Weight weight2) :
		src(src), dst(dst), weight(weight), weight2(weight2) { }
};
bool operator < (const Edge &e, const Edge &f) {
	return make_pair(e.weight, e.weight2) > make_pair(f.weight, f.weight2) // !!INVERSE!!
		|| (make_pair(e.weight, e.weight2) == make_pair(f.weight, f.weight2) && make_pair(e.src, e.dst) < make_pair(f.src, f.dst));
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void shortestPath(const Graph &g, int s,
	vector<Weight> &dist, vector<int> &prev, int C) {
	int n = g.size();
	dist.assign(n, INF); dist[s] = 0;
	prev.assign(n, -1);
	priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
	for (Q.push(Edge(-2, s, 0, 0)); !Q.empty();) {
		Edge e = Q.top(); Q.pop();
		if (prev[e.dst] != -1) continue;
		prev[e.dst] = e.src;
		for (const auto& f : g[e.dst]) {
			if (dist[f.dst] > e.weight + f.weight && C >= e.weight2 + f.weight2) {
				dist[f.dst] = e.weight + f.weight;
				Q.push(Edge(f.src, f.dst, e.weight + f.weight, e.weight2 + f.weight2));
			}
		}
	}
}

int main()
{
	Graph G;
	int N, C, V;
	{
		cin >> N >> C >> V;
		vector<int> S(V), T(V), Y(V), M(V);
		for (int i = 0; i < V; i++) {
			cin >> S[i];
			S[i]--;
		}
		for (int i = 0; i < V; i++) {
			cin >> T[i];
			T[i]--;
		}
		for (int i = 0; i < V; i++) {
			cin >> Y[i];
		}
		for (int i = 0; i < V; i++) {
			cin >> M[i];
		}
		G.assign(N, vector<Edge>());
		for (int i = 0; i < V; i++) {
			G[S[i]].push_back(Edge(S[i], T[i], M[i], Y[i]));
		}
	}
	vector<Weight> dist;
	vector<Weight> prev;
	shortestPath(G, 0, dist, prev, C);
	int ans = dist[N - 1];
	cout << (ans == INF ? -1 : ans) << endl;
	return 0;
}
0