結果
問題 | No.2739 Time is money |
ユーザー |
![]() |
提出日時 | 2024-04-20 16:53:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 2,000 ms |
コード長 | 1,960 bytes |
コンパイル時間 | 2,329 ms |
コンパイル使用メモリ | 204,400 KB |
最終ジャッジ日時 | 2025-02-21 06:55:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define FOR(i, l, r) for(ll i = l; i < r; i++) #define rep(i, n) FOR(i, 0, n) #define FORR(i, l, r) for(ll i = r - 1; i >= l; i--) #define ALL(ar) begin(ar), end(ar) template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; } template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << p.first << ' ' << p.second; return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for(T &x : v) is >> x; return is; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) os << (i ? " " : "") << v[i]; return os; } //------------------------------------------------- void solve() { ll N, M, X; cin >> N >> M >> X; vector<vector<pair<ll, ll>>> g(N); rep(i, M) { ll u, v, c, t; cin >> u >> v >> c >> t; u--; v--; c += t * X; g[u].emplace_back(v, c); g[v].emplace_back(u, c); } vector<ll> dist(N, 1ll << 60); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que; que.emplace(0, 0); dist[0] = 0; while(!que.empty()) { auto [d, v] = que.top(); que.pop(); if(dist[v] < d) continue; for(auto [to, cost] : g[v]) { if(chmin(dist[to], d + cost)) que.emplace(d + cost, to); } } if(dist[N - 1] == 1LL << 60) { cout << -1 << endl; } else { cout << (dist[N - 1] + X - 1) / X << endl; } } int main() { int t = 1; // cin >> t; while(t--) solve(); }