結果
| 問題 |
No.3111 Toll Optimization
|
| コンテスト | |
| ユーザー |
 Yama.can
|
| 提出日時 | 2025-04-20 11:07:24 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 113 ms / 5,000 ms |
| コード長 | 8,206 bytes |
| コンパイル時間 | 9,624 ms |
| コンパイル使用メモリ | 404,168 KB |
| 実行使用メモリ | 20,456 KB |
| 最終ジャッジ日時 | 2025-04-20 11:07:40 |
| 合計ジャッジ時間 | 12,913 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 70 |
ソースコード
#ifndef MAIN
#define MAIN
#include __FILE__
void _main()
{
cint(n, m, k);
cvec(m, c);
cvec(m, u, v);
vector<vector<xy>> g(n);
for (int i = 0; i < m; i++)
{
u[i]--, v[i]--;
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
priority_queue<xyz, vector<xyz>, greater<xyz>> pq;
pq.push({0, 0, 0});
vector<vector<int>> dist(n, vector<int>(k + 1, 1e15));
dist[0][0] = 0;
while (!pq.empty())
{
auto [c, v, dim] = pq.top();
pq.pop();
if (dist[v][dim] < c)
continue;
if (v == n - 1)
{
cout << c << endl;
return;
}
for (auto [nxt, w] : g[v])
{
if (dist[nxt][dim] < w + c)
continue;
dist[nxt][dim] = w + c;
pq.push({w + c, nxt, dim});
if (dim < k)
{
if (dist[nxt][dim + 1] <= c)
continue;
dist[nxt][dim + 1] = c;
pq.push({c, nxt, dim + 1});
}
}
}
cout << -1 << endl;
}
#else
#ifdef DEBUG
#pragma GCC optimize("O0")
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <atcoder/all>
using namespace atcoder;
using modint10 = modint1000000007;
using modint9 = modint998244353;
using namespace std;
template <typename T>
using __ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <typename T>
class orderd_set
: public __ordered_set<T>
{
public:
orderd_set() {}
T operator[](size_t i) const
{
return *__ordered_set<T>::find_by_order(i);
}
size_t indexof(const T &val) const
{
return __ordered_set<T>::order_of_key(val);
}
size_t indexof(__ordered_set<T>::iterator it) const
{
return __ordered_set<T>::order_of_key(*it);
}
size_t count(const T &val) const
{
return indexof(__ordered_set<T>::upper_bound(val)) - indexof(__ordered_set<T>::lower_bound(val));
}
bool contains(const T &val) const
{
return count(val) > 0;
}
void merge(orderd_set<T> &other)
{
if (__ordered_set<T>::size() < other.size())
{
__ordered_set<T>::swap(other);
}
for (const T &val : other)
{
__ordered_set<T>::insert(val);
}
}
};
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<string> strvec;
constexpr ll mod10 = 1000000007;
constexpr ll mod9 = 998244353;
#define int ll
#define double ld
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repf(i, s, n) for (int i = s; i < (int)(n); i++)
#define repr(i, n) for (int i = n - 1; i >= 0; i--)
#define reprt(i, e, n) for (int i = n - 1; i >= e; i--)
#define rep2(i, j, n, m) rep(i, n) rep(j, m)
template <class... Args>
void __y_input(Args &...arg)
{
(cin >> ... >> arg);
}
template <class... Args>
void __y_input_vec_1(int p, Args &...args)
{
(cin >> ... >> args[p]);
}
template <class... Args>
void __y_input_vec_2(int p, int q, Args &...args)
{
(cin >> ... >> args[p][q]);
}
template <class Arg>
void __y_input_vec_resize(int size, Arg &arg)
{
arg.resize(size);
}
template <class Arg_t>
void __y_input_vec_resize_2(int n, int m, vector<Arg_t> &arg)
{
arg.assign(n, Arg_t(m));
}
template <class... Args>
void __y_input_vec(int n, Args &...args)
{
(__y_input_vec_resize(n, args), ...);
rep(i, n)
{
(__y_input_vec_1(i, args), ...);
}
}
template <class... Args>
void __y_input_vec2(int n, int m, Args &...args)
{
(__y_input_vec_resize_2(n, m, args), ...);
rep2(i, j, n, m)
{
(__y_input_vec_2(i, j, args), ...);
}
}
template <class T, class... Args>
void SyncSort(vector<T> &vec, vector<Args> &...args)
{
vector<pair<T, tuple<Args...>>> z;
rep(i, vec.size())
{
z.push_back({vec[i], make_tuple(args.at(i)...)});
}
sort(z.begin(), z.end());
rep(i, vec.size())
{
vec[i] = z[i].first;
tie(args[i]...) = z[i].second;
}
}
#define cint(...) \
int __VA_ARGS__; \
__y_input(__VA_ARGS__)
#define cdbl(...) \
double __VA_ARGS__; \
__y_input(__VA_ARGS__)
#define cstr(...) \
string __VA_ARGS__; \
__y_input(__VA_ARGS__)
#define cit(t, ...) \
t __VA_ARGS__; \
__y_input(__VA_ARGS__)
#define cvec(n, ...) \
vector<int> __VA_ARGS__; \
__y_input_vec(n, __VA_ARGS__)
#define cvect(t, n, ...) \
vector<t> __VA_ARGS__; \
__y_input_vec(n, __VA_ARGS__)
#define cvec2(n, m, ...) \
vector<vector<int>> __VA_ARGS__; \
__y_input_vec2(n, m, __VA_ARGS__)
#define cvec2t(t, n, m, ...) \
vector<vector<t>> __VA_ARGS__; \
__y_input_vec2(n, m, __VA_ARGS__)
#define cvecs(n, ...) cvect(string, n, __VA_ARGS__)
#define yn(bl) (bl ? "Yes" : "No")
#define all(v) v.begin(), v.end()
template <typename T>
using vec2 = vector<vector<T>>;
template <typename T>
using vec3 = vector<vector<vector<T>>>;
template <typename T>
constexpr T limit()
{
return numeric_limits<long long>::max();
}
constexpr ll inf = limit<ll>() / 100;
template <typename T>
constexpr T limit(T _)
{
return numeric_limits<long long>::max();
}
typedef array<int, 2> xy;
typedef array<int, 3> xyz;
template <typename T>
inline void sort(T &vec)
{
return sort(vec.begin(), vec.end());
}
template <typename T>
inline void rsort(T &vec)
{
return sort(vec.rbegin(), vec.rend());
}
template <typename T>
inline vector<vector<T>> rotate90(const vector<vector<T>> &vec)
{
vector<vector<T>> res(vec[0].size(), vector<T>(vec.size()));
rep(i, vec.size())
{
rep(j, vec[0].size())
{
res[j][vec.size() - i - 1] = vec[i][j];
}
}
return res;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
for (T val : vec)
{
os << val << ' ';
}
return os;
}
template <typename T>
vector<T> &operator+=(vector<T> &vec, const T &val)
{
vec.push_back(val);
return vec;
}
template <typename T>
vector<T> &operator+=(vector<T> &vec, const vector<T> &val)
{
vec.insert(vec.end(), val.begin(), val.end());
return vec;
}
template <typename T>
vector<T> &operator+=(vector<T> &vec, const initializer_list<T> &val)
{
vec.insert(vec.end(), val.begin(), val.end());
return vec;
}
template <typename T>
vector<vector<T>> operator*(vector<T> &vec, int val)
{
return vector<vector<T>>(val, vec);
}
void _main();
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(15);
_main();
return 0;
}
// Libraries Begin
class Debugger
{
ostream &os;
public:
Debugger(ostream &os) : os{os} {}
template <typename T>
Debugger &operator,(T val)
{
os << val << ' ';
return *this;
}
Debugger &operator,(char val)
{
os << val;
return *this;
}
template <typename T>
Debugger &operator,(vector<T> vec)
{
*this, '[';
rep(i, vec.size())
{
*this, vec[i], ' ', ", "[i + 1 == vec.size()];
}
*this, "]\n";
return *this;
}
template <typename T, typename U>
Debugger &operator,(map<T, U> mp)
{
*this, "{\n";
for (auto [key, val] : mp)
{
*this, '\t', key, ": ", val, '\n';
}
*this, "}\n";
return *this;
}
template <typename T, typename U>
Debugger &operator,(pair<T, U> p)
{
*this, '(', p.first, ", ", p.second, ')';
return *this;
}
};
Debugger debugger(cerr);
map<int, int> prime_factorize(int n)
{
map<int, int> res;
for (int i = 2; i * i <= n; i += 1 + i > 2)
{
while (n % i == 0)
{
res[i]++;
n /= i;
}
}
if (n != 1)
{
res[n]++;
}
return res;
}
// Libraries End
// Defines
template <typename... T>
common_type_t<T...> __yc_max(T... args)
{
return max(initializer_list<common_type_t<T...>>{args...});
}
template <typename... T>
common_type_t<T...> __yc_min(T... args)
{
return min(initializer_list<common_type_t<T...>>{args...});
}
#define max(...) __yc_max(__VA_ARGS__)
#define min(...) __yc_min(__VA_ARGS__)
// Defines End
#endif
// 自分ここまでよくこのコード書いた！
// __ ====^^==== //===\\ ======= ||=====\\ ||====== ||=====\| +
// //\\ || // \\ // \\ || \| || || || +
// // \\ || || || || || || ||====== ||=====// +
// //====\\ || \\ // \\ // || /| || || \\\ +
// // \\ || \===// \=====// ||=====// ||====== || \\\ +