#1076274 (C++17) No.3111 Toll Optimization

• 問題: No.3111 Toll Optimization
• ユーザー: ROBORU
• 提出日時: 2025-04-19 04:19:03
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 13,045 bytes
• コンパイル時間: 1,949 ms
• コンパイル使用メモリ: 138,040 KB
• 実行使用メモリ: 27,044 KB
• 最終ジャッジ日時: 2025-04-19 04:19:19
• 合計ジャッジ時間: 15,358 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	-- * 3
other	TLE * 1 -- * 69

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cfloat>
#include <climits>
#include <cmath>
#include <numeric>
#include <functional>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;


/// <summary>
/// どれがいくつ入ってるかを高速(?)にソートする。
/// </summary>
/// <typeparam name="T"></typeparam>
template<typename T>
class MultiNum {
	map<T, ll> elementToIdMap;
	map<ll, T> idToElementMap;
	vector<pair<ll, ll>> elementNum;
	vector<pair<ll, ll>> sorted;

public:

	void Add(T element) {
		if (elementToIdMap.count(element) <= 0) {
			elementNum.push_back(pair<ll, ll>(0, elementToIdMap.size()));
			idToElementMap[elementToIdMap.size()] = element;
			elementToIdMap[element] = elementToIdMap.size();
		}
		elementNum[elementToIdMap[element]].first++;
	}

	void SortLess() {
		sorted = elementNum;
		sort(sorted.begin(), sorted.end());
	}
	void SortGreater() {
		sorted = elementNum;
		sort(sorted.begin(), sorted.end(), greater<pair<ll, ll>>());
	}

	vector<pair<T, ll>> GetResult() {
		vector<pair<T, ll>> result;
		for (ll i = 0; i < sorted.size(); i++) {
			result.push_back(pair<T, ll>(idToElementMap[sorted[i].second], sorted[i].first));
		}

		return result;
	}
};

class nCk {
	const ll divs;
	const ll maxSize;
	vector<ll> fac;
	vector<ll> invFac;


	ll divsPow(ll base, ll exponent) {
		ll answer = 1;

		while (0 < exponent) {
			if (exponent & 1) {
				answer = (answer * base) % divs;
				exponent--;
				continue;
			}

			base = (base * base) % divs;
			exponent = exponent >> 1;
		}

		return answer;
	}

public:
	nCk(ll _divs, ll _max) : divs(_divs), maxSize(_max) {
		//index0,1は全て1と考えられる。
		fac.push_back(1);
		fac.push_back(1);
		invFac.push_back(1);
		invFac.push_back(1);

		for (ll i = 2; i <= maxSize; i++) {
			fac.push_back((fac[i - 1] * i) % divs);
			invFac.push_back((invFac[i - 1] * divsPow(i, divs - 2)) % divs);
		}
	}

	ll Execute(ll n, ll k) {
		if (n < k) return 0;
		if (n < 0 || k < 0) return 0;
		return (fac[n] * ((invFac[k] * invFac[n - k]) % divs)) % divs;
	}
};


template<typename Ty>
class IdMap {

	set<Ty> _isExist;
	map<Ty, ll> _map;
	function<void(Ty)> _newIdAction;


public:
	IdMap(function<void(Ty)> newIdAction) {
		_newIdAction = newIdAction;
	}

	ll getId(Ty id) {
		if (_isExist.count(id) <= 0) {
			_isExist.insert(id);
			_map[id] = _map.size();
			_newIdAction(id);
		}
		return _map[id];
	}
};




class UnionFind {
private:
	vector<int> parent;

public:
	UnionFind(int size) : parent(size, -1) {
		//		iota(parent.begin(), parent.end(), -1);
	}


	int FindRoot(int v) {
		// -1ならrootは自分になる。
		if (parent[v] < 0) return v;
		// root更新していく
		parent[v] = FindRoot(parent[v]);
		return parent[v];
	}

	void Unite(int a, int b) {
		int rootA = FindRoot(a);
		int rootB = FindRoot(b);
		// rootが同じなら何もしない。
		if (rootA == rootB) return;
		parent[rootB] = rootA;
	}

	bool IsSameRoot(int a, int b) {
		if (FindRoot(a) == FindRoot(b)) return true;
		else return false;
	}

};

template<typename T>
class SegmentTree {
	vector<T> e;
	size_t size;
	function<T(T, T)> calc;
	const T identity;

	size_t get_new_size(size_t prevSize) {
		size_t newSize = 1;
		for (; newSize < prevSize; newSize *= 2) {}
		return newSize;
	}

	size_t get_eId(size_t id) {
		return id + size;
	}

	void updateFromChildren(size_t eId) {
		if (eId == 0) return;
		e[eId] = calc(e[eId * 2], e[eId * 2 + 1]);
		updateFromChildren(eId / 2);
	}

	T getRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed) {
		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return identity;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			return e[eId];
		}

		// まだ絞り切れてない
		return
			calc(
				getRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed),
				getRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed)
			);
	}

public:
	SegmentTree(size_t _size, T initNum, function<T(T, T)> _calc) :
		size(get_new_size(_size)),
		identity(initNum),
		calc(_calc)
	{
		e.resize(2 * size, identity);
	}

	void update(size_t id, T newValue) {
		auto elementId = get_eId(id);
		e[elementId] = newValue;
		updateFromChildren(elementId / 2);
	}

	T getOne(size_t id) {
		return e[get_eId(id)];
	}

	/// <summary>
	/// [leftId, rightId)
	/// </summary>
	T getRange(size_t leftId, size_t rightId) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return getRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId);
	}
};

template<typename T>
class LazySegmentTree {
	vector<T> e;
	vector<T> lazyE;
	vector<bool> hasLazyValue;
	size_t size;
	function<T(T, T)> calc;
	function<T(T, T)> operateByLazy;
	const T identity;

	size_t get_new_size(size_t prevSize) {
		size_t newSize = 1;
		for (; newSize < prevSize; newSize *= 2) {}
		return newSize;
	}

	size_t get_eId(size_t id) {
		return id + size;
	}

	void updateRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed, T newValue) {
		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			e[eId] = operateByLazy(e[eId], newValue);
			if (eId < size) {
				lazyE[eId * 2] = newValue;
				lazyE[eId * 2 + 1] = newValue;
				hasLazyValue[eId * 2] = true;
				hasLazyValue[eId * 2 + 1] = true;
			}
			return;
		}

		// まだ絞り切れてない
		updateRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed, newValue);
		updateRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed, newValue);
		// 子のupdateに応じて親をupdateさせる
		e[eId] = calc(e[eId * 2], e[eId * 2 + 1]);
	}

	T getRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed) {
		//lazy評価
		if (hasLazyValue[eId]) {
			e[eId] = operateByLazy(e[eId], lazyE[eId]);
			hasLazyValue[eId] = false;
			// 子がいるなら子にも伝搬する
			if (eId < size) {
				lazyE[eId * 2] = lazyE[eId];
				lazyE[eId * 2 + 1] = lazyE[eId];
				hasLazyValue[eId * 2] = true;
				hasLazyValue[eId * 2 + 1] = true;
			}
		}

		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return identity;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			return e[eId];
		}

		// まだ絞り切れてない
		e[eId] = calc(
			getRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed),
			getRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed)
		);
		return e[eId];
	}

public:
	LazySegmentTree(size_t _size, T initNum, function<T(T, T)> _calc, function<T(T, T)> _operateByLazy) :
		size(get_new_size(_size)),
		identity(initNum),
		calc(_calc),
		operateByLazy(_operateByLazy)
	{
		e.resize(2 * size, identity);
		lazyE.resize(2 * size, identity);
		hasLazyValue.resize(2 * size, false);
	}

	void updateRange(size_t leftId, size_t rightId, T newValue) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return updateRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId, newValue);
	}

	void update(size_t id, T newValue) {
		updateRange(id, id + 1, newValue);
	}

	/// <summary>
	/// [leftId, rightId)
	/// </summary>
	T getRange(size_t leftId, size_t rightId) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return getRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId);
	}

	T getOne(size_t id) {
		return getRange(id, id + 1);
	}
};

class scc {
	ll n;
	vector<vector<ll>> groups;

	void searchMe(ll id, ll& nowScore, vector<ll>& score, vector<vector<ll>>& edge) {
		if (0 <= score[id]) return;
		score[id] = 0;

		for (auto& p : edge[id]) {
			searchMe(p, nowScore, score, edge);
		}
		score[id] = nowScore++;
	}

	void reverseSearchMe(ll id, vector<ll>& cameIds, vector<bool>& hasCame, vector<vector<ll>>& edge) {
		if (hasCame[id]) return;
		hasCame[id] = true;
		cameIds.push_back(id);
		for (auto& p : edge[id]) {
			reverseSearchMe(p, cameIds, hasCame, edge);
		}
	}

public:
	scc(ll _n, vector<pair<ll, ll>> _edge) : n(_n) {
		vector<vector<ll>> edge(n), backE(n);
		for (auto& e : _edge) {
			edge[e.first].push_back(e.second);
			backE[e.second].push_back(e.first);
		}

		vector<ll> score(n, -1);
		ll nowScore = 0;
		for (ll i = 0; i < n; i++) {
			searchMe(i, nowScore, score, edge);
		}

		vector<ll> idScore(n, -1);
		for (ll i = 0; i < n; i++) {
			idScore[score[i]] = i;
		}

		vector<bool> hasCame(n, false);
		for (ll i = n - 1; 0 <= i; i--) {
			vector<ll> cameIds;
			reverseSearchMe(idScore[i], cameIds, hasCame, backE);
			groups.push_back(cameIds);
		}
	}

	vector<vector<ll>>& getGroups() {
		return groups;
	}
};

template<typename T>
class queueVec {
	ll sItr, eItr;
	vector<T> vec;
public:
	queueVec(ll capacity) {
		sItr = 0;
		eItr = 0;
		vec.reserve(capacity);
	}

	ll size() {
		return eItr - sItr;
	}

	void push(T value) {
		eItr++;
		vec.emplace_back(value);
	}

	void pop() {
		sItr++;
	}

	T front() {
		return vec[sItr];
	}
};

class Lca {
	vector<vector<ll>> parents;
	vector<vector<ll>> es;
	vector<ll> depths;
	ll maxDepthLog2;

public:
	Lca(ll n, vector<pair<ll, ll>>& edges) {
		ll kaisou = log2l(n - 1) + 1;
		parents = vector<vector<ll>>(n, vector<ll>(kaisou, -1));
		depths = vector<ll>(n);

		// make tree
		{
			es = vector<vector<ll>>(n);
			for (auto& e : edges) {
				es[e.first].push_back(e.second);
				es[e.second].push_back(e.first);
			}

			parents[0][0] = 0;
			queueVec<ll> queueP(n);
			queueP.push(0);
			ll d = 0;
			for (d = 0; 0 < queueP.size(); d++) {
				ll qNum = queueP.size();
				for (ll q = 0; q < qNum; q++) {
					auto p = queueP.front();
					queueP.pop();
					depths[p] = d;

					for (auto& np : es[p]) {
						if (parents[np][0] < 0) {
							parents[np][0] = p;
							queueP.push(np);
						}
					}
				}
			}
			maxDepthLog2 = (ll)log2l(d - 1) + 1;

			for (ll k = 1; k < kaisou; k++) {
				for (ll i = 0; i < n; i++) {
					parents[i][k] = parents[parents[i][k - 1]][k - 1];
				}
			}
		}
	}

	ll getAncestor(ll v, ll steps) {
		for (ll k = 0, k2 = 1; k2 <= steps; k++, k2 *= 2) {
			if (0 < (k2 & steps)) {
				v = parents[v][k];
			}
		}
		return v;
	}

	ll commonAncestor(ll a, ll b) {
		if (depths[a] < depths[b]) {
			b = getAncestor(b, depths[b] - depths[a]);
		}
		else if (depths[b] < depths[a]) {
			a = getAncestor(a, depths[a] - depths[b]);
		}

		if (a == b) return a;
		for (ll k = maxDepthLog2; 0 <= k; k--) {
			if (parents[a][k] == parents[b][k]) continue;
			a = parents[a][k];
			b = parents[b][k];
		}

		return parents[a][0];
	}

	ll distance(ll a, ll b) {
		return depths[a] + depths[b] - 2 * depths[commonAncestor(a, b)];
	}

	pair<ll, ll> diameterVs() {
		ll v;
		ll maxD = -1;
		for (ll i = 0; i < depths.size(); i++) {
			if (maxD < depths[i]) {
				maxD = depths[i];
				v = i;
			}
		}

		pair<ll, ll> answer = { v, v };
		ll farV = -1;
		queueVec<ll> nextP(depths.size());
		vector<bool> isReached(depths.size(), false);
		nextP.push(v);
		isReached[v] = true;
		while (0 < nextP.size()) {
			ll qSize = nextP.size();
			for (ll q = 0; q < qSize; q++) {
				auto p = nextP.front();
				nextP.pop();
				farV = p;
				for (auto& np : es[p]) {
					if (isReached[np]) continue;
					isReached[np] = true;
					nextP.push(np);
				}
			}
		}
		answer.second = farV;
		return answer;
	}
};


int main()
{
	ll n, m, k;
	cin >> n >> m >> k;

	vector<ll> c(m);
	for (ll i = 0; i < m; i++) cin >> c[i];
	vector<map<ll, ll>> uv(n);
	for (ll i = 0; i < m; i++) {
		ll u, v;
		cin >> u >> v;
		u--; v--;
		uv[u][v] = i;
		uv[v][u] = i;
	}

	vector<vector<ll>> dp(n, vector<ll>(k + 1, LLONG_MAX));

	{
		stack<pair<ll, ll>> pStack;
		pStack.push({ 0, 0 });

		while (0 < pStack.size()) {
			auto nowp = pStack.top();
			pStack.pop();

			if (dp[nowp.first][0] <= nowp.second) continue;
			dp[nowp.first][0] = nowp.second;

			for (auto& p : uv[nowp.first]) {
				pStack.push({ p.first, nowp.second + c[uv[nowp.first][p.first]] });
			}
		}
	}

	for (ll kk = 0; kk < k; kk++) {
		priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pStack;
		dp[0][kk + 1] = 1000000000000000;
		pStack.push({ 0, 0 });

		while (0 < pStack.size()) {
			auto nowp = pStack.top();
			pStack.pop();

			for (auto& p : uv[nowp.second]) {
				ll nextScore = min(dp[nowp.second][kk], dp[nowp.second][kk + 1] + c[uv[nowp.second][p.first]]);
				if (dp[p.first][kk + 1] <= nextScore) continue;
				dp[p.first][kk + 1] = nextScore;
				pStack.push({ nextScore, p.first });
			}
		}
	}

	ll answer = LLONG_MAX;
	for (auto& co : dp[n - 1]) answer = min(answer, co);
	if (answer == LLONG_MAX) answer = -1;
	cout << answer << endl;
}