結果
| 問題 | No.3653 Space-Time Courier |
| コンテスト | |
| ユーザー |
 ぽえ
|
| 提出日時 | 2026-08-28 21:47:33 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 266 ms / 4,000 ms |
| + 234µs | |
| コード長 | 9,504 bytes |
| 記録 | |
| コンパイル時間 | 3,803 ms |
| コンパイル使用メモリ | 460,084 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-08-28 21:47:54 |
| 合計ジャッジ時間 | 7,827 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#line 1 "main.cpp"
#include <bits/stdc++.h>
using namespace std;
#include <immintrin.h>
#line 2 "/home/mackerel38/kyopro/vendor/nyaan-library/shortest-path/bellman-ford.hpp"
#line 2 "/home/mackerel38/kyopro/vendor/nyaan-library/graph/graph-template.hpp"
template <typename T>
struct edge {
int src, to;
T cost;
edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;
// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
UnweightedGraph g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
if (is_1origin) x--, y--;
g[x].push_back(y);
if (!is_directed) g[y].push_back(x);
}
return g;
}
// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
WeightedGraph<T> g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
cin >> c;
if (is_1origin) x--, y--;
g[x].emplace_back(x, y, c);
if (!is_directed) g[y].emplace_back(y, x, c);
}
return g;
}
// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
bool is_1origin = true) {
Edges<T> es;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
es.emplace_back(x, y, c);
}
return es;
}
// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
bool is_directed = false, bool is_1origin = true) {
vector<vector<T>> d(N, vector<T>(N, INF));
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
d[x][y] = c;
if (!is_directed) d[y][x] = c;
}
return d;
}
/**
* @brief グラフテンプレート
* @docs docs/graph/graph-template.md
*/
#line 6 "/home/mackerel38/kyopro/vendor/nyaan-library/shortest-path/bellman-ford.hpp"
// bellman-ford法
// goalが存在しないとき-> 負閉路が存在するときは空列を返す
// goalが存在するとき -> startとgoalの間に負閉路が存在する時に負閉路を返す
template <typename T>
vector<T> bellman_ford(int N, Edges<T> &es, int start = 0, int goal = -1) {
T INF = numeric_limits<T>::max() / 2;
vector<T> d(N, INF);
d[start] = 0;
for (int i = 0; i < N; i++) {
bool update = false;
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost) {
update = true, d[e.to] = d[e.src] + e.cost;
}
}
if (!update) return d;
}
if (goal == -1) return vector<T>();
vector<bool> negative(N, false);
for (int i = 0; i < N; i++) {
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost)
negative[e.to] = true, d[e.to] = d[e.src] + e.cost;
if (negative[e.src] == true) negative[e.to] = true;
}
}
if (negative[goal] == true)
return vector<T>();
else
return d;
}
#line 2 "/home/mackerel38/kyopro/vendor/nyaan-library/shortest-path/dijkstra-fast.hpp"
#line 2 "/home/mackerel38/kyopro/vendor/nyaan-library/data-structure/radix-heap.hpp"
template <typename Key, typename Val>
struct RadixHeap {
using uint = typename make_unsigned<Key>::type;
static constexpr int bit = sizeof(Key) * 8;
array<vector<pair<uint, Val> >, bit + 1> vs;
array<uint, bit + 1> ms;
int s;
uint last;
RadixHeap() : s(0), last(0) { fill(begin(ms), end(ms), uint(-1)); }
bool empty() const { return s == 0; }
int size() const { return s; }
__attribute__((target("lzcnt"))) inline uint64_t getbit(uint a) const {
return 64 - _lzcnt_u64(a);
}
void push(const uint &key, const Val &val) {
s++;
uint64_t b = getbit(key ^ last);
vs[b].emplace_back(key, val);
ms[b] = min(key, ms[b]);
}
pair<uint, Val> pop() {
if (ms[0] == uint(-1)) {
int idx = 1;
while (ms[idx] == uint(-1)) idx++;
last = ms[idx];
for (auto &p : vs[idx]) {
uint64_t b = getbit(p.first ^ last);
vs[b].emplace_back(p);
ms[b] = min(p.first, ms[b]);
}
vs[idx].clear();
ms[idx] = uint(-1);
}
--s;
auto res = vs[0].back();
vs[0].pop_back();
if (vs[0].empty()) ms[0] = uint(-1);
return res;
}
};
/**
* @brief Radix Heap
* @docs docs/data-structure/radix-heap.md
*/
#line 2 "/home/mackerel38/kyopro/vendor/nyaan-library/graph/static-graph.hpp"
namespace StaticGraphImpl {
template <typename T, bool Cond = is_void<T>::value>
struct E;
template <typename T>
struct E<T, false> {
int to;
T cost;
E() {}
E(const int& v, const T& c) : to(v), cost(c) {}
operator int() const { return to; }
};
template <typename T>
struct E<T, true> {
int to;
E() {}
E(const int& v) : to(v) {}
operator int() const { return to; }
};
template <typename T = void>
struct StaticGraph {
private:
template <typename It>
struct Es {
It b, e;
It begin() const { return b; }
It end() const { return e; }
int size() const { return int(e - b); }
auto&& operator[](int i) const { return b[i]; }
};
int N, M, ec;
vector<int> head;
vector<pair<int, E<T>>> buf;
vector<E<T>> es;
void build() {
partial_sum(begin(head), end(head), begin(head));
es.resize(M);
for (auto&& [u, e] : buf) es[--head[u]] = e;
}
public:
StaticGraph(int _n, int _m) : N(_n), M(_m), ec(0), head(N + 1, 0) {
buf.reserve(M);
}
template <typename... Args>
void add_edge(int u, Args&&... args) {
#pragma GCC diagnostic ignored "-Wnarrowing"
buf.emplace_back(u, E<T>{std::forward<Args>(args)...});
#pragma GCC diagnostic warning "-Wnarrowing"
++head[u];
if ((int)buf.size() == M) build();
}
Es<typename vector<E<T>>::iterator> operator[](int u) {
return {begin(es) + head[u], begin(es) + head[u + 1]};
}
const Es<typename vector<E<T>>::const_iterator> operator[](int u) const {
return {begin(es) + head[u], begin(es) + head[u + 1]};
}
int size() const { return N; }
};
} // namespace StaticGraphImpl
using StaticGraphImpl::StaticGraph;
/**
* @brief Static Graph
* @docs docs/graph/static-graph.md
*/
#line 5 "/home/mackerel38/kyopro/vendor/nyaan-library/shortest-path/dijkstra-fast.hpp"
template <typename T>
vector<T> dijkstra(StaticGraph<T>& g, int start = 0) {
vector<T> d(g.size(), T(-1));
RadixHeap<T, int> Q;
d[start] = 0;
Q.push(0, start);
while (!Q.empty()) {
auto p = Q.pop();
int u = p.second;
if (d[u] < T(p.first)) continue;
T du = d[u];
for (auto&& [v, c] : g[u]) {
if (d[v] == T(-1) || du + c < d[v]) {
d[v] = du + c;
Q.push(d[v], v);
}
}
}
return d;
}
template <typename T>
T dijkstra_point(StaticGraph<T>& g, int start, int goal) {
vector<T> d(g.size(), T(-1));
RadixHeap<T, int> Q;
d[start] = 0;
Q.push(0, start);
while (!Q.empty()) {
auto p = Q.pop();
int u = p.second;
if(u == goal) return d[u];
if (d[u] < T(p.first)) continue;
T du = d[u];
for (auto&& [v, c] : g[u]) {
if (d[v] == T(-1) || du + c < d[v]) {
d[v] = du + c;
Q.push(d[v], v);
}
}
}
return -1;
}
template <typename T>
vector<pair<T, int>> dijkstra_restore(StaticGraph<T>& g, int start = 0) {
vector<pair<T, int>> d(g.size(), {T(-1), -1});
RadixHeap<T, int> Q;
d[start] = {0, -1};
Q.push(0, start);
while (!Q.empty()) {
auto p = Q.pop();
int u = p.second;
if (d[u].first < T(p.first)) continue;
T du = d[u].first;
for (auto&& [v, c] : g[u]) {
if (d[v].first == T(-1) || du + c < d[v].first) {
d[v] = {du + c, u};
Q.push(du + c, v);
}
}
}
return d;
}
/*
* @brief ダイクストラ法(定数倍高速化)
* @docs docs/shortest-path/dijkstra-fast.md
**/
#line 7 "main.cpp"
using ll = long long;
const ll inf = numeric_limits<ll>::max() / 2;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<ll> p(n); for (auto& x : p) cin >> x;
Edges<ll> es;
vector<tuple<int, int, ll>> ori;
ori.reserve(m);
for (int i=0; i<m; i++) {
int u, v; ll t; cin >> u >> v >> t; u--; v--;
es.emplace_back(u, v, t);
ori.emplace_back(u, v, t);
}
for (int i=0; i<n; i++) es.emplace_back(n, i, 0);
auto h_all = bellman_ford<ll>(n+1, es, n);
vector<ll> h(n);
for (int i=0; i<n; i++) h[i] = h_all[i];
StaticGraph<ll> g(n, m);
for (auto& [u, v, w] : ori) g.add_edge(u, v, w + h[u]-h[v]);
ll ans = inf;
ll cnt = 0;
for (int s=0; s<n; s++) {
auto d = dijkstra(g, s);
for (int t=0; t<n; t++) if (s != t) if (d[t] != -1){
ll dist = d[t] - h[s] + h[t];
ll cost = p[s] + dist + p[t];
if (cost < ans) {
ans = cost;
cnt = 1;
} else if (cost == ans) cnt++;
}
}
if (ans == inf) cout << -1 << '\n';
else cout << ans << ' ' << cnt << '\n';
}