結果

問題 No.3111 Toll Optimization
ユーザー kkk
提出日時 2025-04-19 12:17:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 215 ms / 5,000 ms
コード長 3,322 bytes
コンパイル時間 4,091 ms
コンパイル使用メモリ 264,180 KB
実行使用メモリ 20,288 KB
最終ジャッジ日時 2025-04-19 12:17:56
合計ジャッジ時間 11,354 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace atcoder;
using namespace std;
using ll = long long;
// --------------------------------------------------------
template <class T>
bool chmax(T &a, const T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#define FOR(i, l, r) for (ll i = (l); i < (r); ++i)
#define RFOR(i, l, r) for (ll i = (r) - 1; (l) <= i; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0LL)
#define BITCNT(c) __builtin_popcountll(c)
#define SZ(c) ((int)(c).size())
#define COUT(c) cout << (c) << '\n'
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<ll, ll>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
static const double EPS = 1e-10;
static const double PI = acos(-1.0);
template <typename T>
void arrPrint(vector<T> arr) {
  for (auto v : arr) cout << v << " ";
  cout << '\n';
}
template <typename T>
void arrPrint2Dim(vector<vector<T>> arr) {
  for (auto a : arr) arrPrint(a);
}
template <typename T, typename T2>
void arrPrintPair(vector<pair<T, T2>> arr) {
  for (auto v : arr) cout << "{" << v.first << "," << v.second << "}, ";
  cout << '\n';
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// static const int INF = (1 << 30) - 1;  // 1073741824 - 1
static const ll INF = (1LL << 62) - 1;  // 4611686018427387904 - 1
// static const ll MOD = 1000000007;
static const ll MOD = 998244353;
using mint = static_modint<MOD>;
using VM = vector<mint>;
using VVM = vector<VM>;
ostream &operator<<(std::ostream &os, const mint &n) { return os << n.val(); }
ll llceil(ll a, ll b) { return (a + b - 1) / b; }
using T = tuple<ll, ll, ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll N, M, K;
  cin >> N >> M >> K;
  VLL Cost(M);
  VVP to(N);
  REP(i, M) cin >> Cost[i];
  REP(i, M) {
    ll u, v;
    cin >> u >> v;
    --u, --v;
    to[u].push_back({v, Cost[i]});
    to[v].push_back({u, Cost[i]});
  }
  VVLL dist(N, VLL(K + 1, INF));
  priority_queue<T, vector<T>, greater<T>> que;
  dist[0][0] = 0;
  que.push({0, 0, 0});
  while (!que.empty()) {
    auto [d, v, useCount] = que.top();
    que.pop();
    if (dist[v][useCount] < d) continue;
    for (auto [nv, c] : to[v]) {
      // クーポンを利用する
      if (useCount < K && chmin(dist[nv][useCount + 1], d)) {
        que.push({dist[nv][useCount + 1], nv, useCount + 1});
      }
      // クーポンを利用しない
      if (chmin(dist[nv][useCount], d + c)) {
        que.push({dist[nv][useCount], nv, useCount});
      }
    }
  }
  ll ans = INF;
  REP(k, K + 1) chmin(ans, dist[N - 1][k]);
  if (ans == INF) ans = -1;
  COUT(ans);
}
0