#1180223 (C++23) No.3653 Space-Time Courier

• 問題: No.3653 Space-Time Courier
• ユーザー: kwm_t
• 提出日時: 2026-08-29 03:05:56
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 627 ms / 4,000 ms
• コード長: 6,402 bytes
• コンパイル時間: 2,999 ms
• コンパイル使用メモリ: 355,552 KB
• 実行使用メモリ: 53,120 KB
• 最終ジャッジ日時: 2026-08-29 03:06:06
• 合計ジャッジ時間: 9,775 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 28

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_GRAPH_SHORTEST_PATH_DIJKSTRA_HPP
#define KWM_T_GRAPH_SHORTEST_PATH_DIJKSTRA_HPP

#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <functional>
#include <algorithm>

/**
 * @brief ダイクストラ法（単一始点最短路 + 経路復元用情報）
 *
 * 非負重みグラフにおける単一始点最短路を求める。
 * prev を用いることで最短経路の復元が可能。
 *
 * 典型用途:
 *   - 重み付きグラフ（非負）
 *   - グリッド + コスト
 *   - 最短経路 + 経路復元
 *
 * 計算量:
 *   O((V + E) log V)
 *
 * @tparam T 距離型（int, long long など）
 *
 * @param g 隣接リスト (to, cost)
 * @param s 始点
 * @param inf 無限大
 *
 * @return pair(dist, prev)
 *
 * 制約 / 注意:
 *   - 負辺がある場合は使用不可（Bellman-Fordを使う）
 *
 * 使用例:
 *   auto [dist, prev] = dijkstra(g, s, INF);
 *   auto path = restore_path(prev, s, t);
 *
 * verified:
 *   https://atcoder.jp/contests/awc0033/submissions/74392079
 */
namespace kwm_t::graph::shortest_path {

template<typename T>
std::pair<std::vector<T>, std::vector<int>>
dijkstra(const std::vector<std::vector<std::pair<int, T>>>& g, int s, T inf) {
	int n = (int)g.size();

	std::vector<T> dist(n, inf);
	std::vector<int> prev(n, -1);

	using S = std::pair<T, int>;
	std::priority_queue<S, std::vector<S>, std::greater<S>> pq;

	dist[s] = 0;
	pq.emplace(0, s);

	while (!pq.empty()) {
		auto [d, v] = pq.top();
		pq.pop();

		if (d > dist[v]) continue;

		for (auto [to, cost] : g[v]) {
			if (dist[v] > inf - cost) continue; // overflow guard

			T nd = dist[v] + cost;
			if (nd < dist[to]) {
				dist[to] = nd;
				prev[to] = v;
				pq.emplace(nd, to);
			}
		}
	}

	return { dist, prev };
}

/**
 * @brief 経路復元
 * @param prev dijkstra で得た prev
 * @param s 始点
 * @param t 終点
 * @return s -> t の最短経路（存在しない場合は空）
 */
inline std::vector<int>
restore_path(const std::vector<int>& prev, int s, int t) {
	std::vector<int> path;
	for (int v = t; v != -1; v = prev[v]) {
		path.push_back(v);
	}
	std::reverse(path.begin(), path.end());

	if (path.empty() || path[0] != s) return {};
	return path;
}

} // namespace kwm_t::graph::shortest_path

#endif // KWM_T_GRAPH_SHORTEST_PATH_DIJKSTRA_HPP

#ifndef KWM_T_GRAPH_SHORTEST_PATH_JOHNSON_HPP
#define KWM_T_GRAPH_SHORTEST_PATH_JOHNSON_HPP

#include <vector>
#include <utility>

// #include "dijkstra.hpp"

/**
 * @brief Johnson's Algorithm（負辺対応・全点対最短路）
 *
 * 負辺を含む有向グラフに対して、全頂点対の最短距離を求める。
 * 負閉路が存在しないことを仮定する。
 *
 * 全頂点を初期距離 0 とした Bellman-Ford 法でポテンシャルを計算し、
 * 各辺を非負重みに変換した後、各頂点から Dijkstra 法を実行する。
 *
 * 典型用途:
 *   - 負辺を含むグラフの全点対最短路
 *   - 疎グラフの全点対最短路
 *
 * 計算量:
 *   O(VE + V(V + E) log V)
 *
 * @tparam T 距離・辺重みの型
 *
 * @param g 隣接リスト (to, cost)
 * @param inf 無限大
 *
 * @return dist[i][j]
 *   頂点 i から頂点 j への最短距離。
 *   到達不能な場合は inf。
 *
 * 制約 / 注意:
 *   - 負閉路が存在しないこと
 *   - inf は十分大きな値を指定すること
 *
 * 使用例:
 *   using T = long long;
 *
 *   std::vector<std::vector<std::pair<int, T>>> g(n);
 *   g[0].emplace_back(1, -5);
 *   g[1].emplace_back(2, 10);
 *
 *   auto dist = johnson(g, INF);
 *
 * verified:
 *   未verified
 */
namespace kwm_t::graph::shortest_path {

template<typename T>
std::vector<std::vector<T>> johnson(const std::vector<std::vector<std::pair<int, T>>>& g, T inf) {

	const int n = (int)g.size();

	// 1. ポテンシャルの計算
	// 超頂点から全頂点へ重み 0 の辺を張る代わりに、
	// 全頂点の初期距離を 0 として Bellman-Ford を行う。
	std::vector<T> h(n, 0);
	for (int i = 0; i < n - 1; ++i) {
		bool updated = false;
		for (int u = 0; u < n; ++u) {
			for (auto [v, cost] : g[u]) {
				if (h[u] + cost < h[v]) {
					h[v] = h[u] + cost;
					updated = true;
				}
			}
		}
		if (!updated) break;
	}

	// 2. 辺の重みを非負化
	// new_cost = cost + h[u] - h[v]
	std::vector<std::vector<std::pair<int, T>>> reweighted_g(n);

	for (int u = 0; u < n; ++u) {
		reweighted_g[u].reserve(g[u].size());

		for (auto [v, cost] : g[u]) {
			T new_cost = cost + h[u] - h[v];
			reweighted_g[u].emplace_back(v, new_cost);
		}
	}

	// 3. 各頂点から Dijkstra
	std::vector<std::vector<T>> dist(n, std::vector<T>(n, inf));

	for (int s = 0; s < n; ++s) {
		auto [d, prev] = dijkstra(reweighted_g, s, inf);

		for (int t = 0; t < n; ++t) {
			if (d[t] >= inf) continue;

			// 元の距離へ復元
			dist[s][t] = d[t] - h[s] + h[t];
		}
	}
	return dist;
}

} // namespace kwm_t::graph::shortest_path

#endif // KWM_T_GRAPH_SHORTEST_PATH_JOHNSON_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<int>p(n);
	rep(i, n)cin >> p[i];
	vector g(n, vector<pair<int, long long>>());
	rep(i, m) {
		int u, v, t; cin >> u >> v >> t;
		u--, v--;
		g[u].emplace_back(v, t);
	}
	auto dist = kwm_t::graph::shortest_path::johnson(g, LINF);
	long long ans = LINF;
	int cnt = 0;
	rep(i, n)rep(j, n)if (i != j) {
		auto d = dist[i][j] + p[i] + p[j];
		if (chmin(ans, d))cnt = 0;
		if (ans == d)cnt++;
	}
	cout << ans << "  " << cnt << endl;
	return 0;
}