結果
問題 | No.2739 Time is money |
ユーザー |
|
提出日時 | 2024-04-21 02:26:39 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,717 bytes |
コンパイル時間 | 1,504 ms |
コンパイル使用メモリ | 139,180 KB |
実行使用メモリ | 22,532 KB |
最終ジャッジ日時 | 2024-10-13 00:57:23 |
合計ジャッジ時間 | 7,551 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 TLE * 1 -- * 4 |
ソースコード
#pragma region my_template #include <algorithm> #include <bitset> #include <cassert> #include <climits> #include <cmath> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <tuple> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using ll = long long; using pi = pair<int, int>; using pl = pair<ll, ll>; using ti = tuple<int, int, int>; using tl = tuple<ll, ll, ll>; using vi = vector<int>; using vpi = vector<pi>; using vti = vector<ti>; using vvi = vector<vi>; using usi = unordered_set<int>; using vl = vector<ll>; using vpl = vector<pl>; using vtl = vector<tl>; using vvl = vector<vl>; using usl = unordered_set<ll>; #define range(i, l, r) for(int i = (int)(l); i < (int)(r); i++) #define rrange(i, l, r) for(int i = (int)(r)-1; i >= (int)(l); i--) #define rep(i, n) range(i, 0, n) #define rrep(i, n) rrange(i, 0, n) #define len(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sum(a) accumulate(all(a), 0) #define it2idx(a, it) distance(a.begin(), it) #define idx2it(a, idx) next(a.begin(), idx) #define elif else if namespace io { #ifdef LOCAL ofstream dout("./dmp.txt"); #else ofstream dout("/dev/null"); #endif template<typename T, typename U> istream &operator >> (istream &in, pair<T, U> &a){ in >> a.first >> a.second; return in; } template<typename T> istream &operator >> (istream &in, vector<T> &a){ for(T &x: a) in >> x; return in; } template<typename T, typename U> ostream &operator << (ostream &out, const pair<T, U> &a){ out << a.first << " " << a.second; return out; } template<typename T> ostream &operator << (ostream &out, const vector<T> &a) { rep(i, len(a)) out << a[i] << (i == len(a)-1 ? "" : " "); return out; } template<typename T> ostream &operator << (ostream &out, const unordered_set<T> &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } template<typename T> ostream &operator << (ostream &out, const set<T> &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } template<typename T> ostream &operator << (ostream &out, const multiset<T> &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } inline void print() { cout << "\n"; } template <typename T, typename ...U> inline void print(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << " "; print(u...); } inline void dmp() { dout << endl; } template <typename T, typename ...U> inline void dmp(const T &t, const U &...u) { dout << t; if (sizeof...(u)) dout << " "; dmp(u...); } } using namespace io; template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } void solve(); constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr int MOD = 1e9+7; //constexpr int MOD = 998244353; int main() { cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15); solve(); return 0; } #pragma endregion int n, m, x; vl dijkstra(const vector<vti> &g, int s) { vl d(n, LINF); vl rem(n, 0); priority_queue<pl, vpl, greater<pl>> q; d[s] = 0; q.emplace(make_pair(0, s)); while (!q.empty()) { auto [time, v] = q.top(); q.pop(); if (d[v] < time) continue; for (auto &[nv, value, t]: g[v]) { ll cost = t; ll wt = 0; if (rem[v] < value) { wt = (value-rem[v]+x-1)/x; cost += wt; } ll r = rem[v] + wt*x-value; if (d[nv] > d[v] + cost or (d[nv] == d[v]+cost and rem[nv] < r)) { d[nv] = d[v] + cost; rem[nv] = r; q.emplace(make_pair(d[nv], nv)); } } } return d; } void solve() { cin >> n >> m >> x; vector<vti> graph(n); rep(_, m) { int u, v, c, t; cin >> u >> v >> c >> t; u--; v--; graph[u].emplace_back(v, c, t); graph[v].emplace_back(u, c, t); } ll res = dijkstra(graph, 0)[n-1]; print(res == LINF ? -1 : res); }