結果

問題 No.2739 Time is money
ユーザー sk4rdsk4rd
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
}
0