結果

問題 No.2739 Time is money
ユーザー iroha HEFFERNAN
提出日時 2024-04-21 12:45:16
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 471 ms / 2,000 ms
コード長 3,933 bytes
コンパイル時間 2,443 ms
コンパイル使用メモリ 207,788 KB
最終ジャッジ日時 2025-02-21 08:06:01
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*＿＿＿＿＿＿
　　 ||　　　　  　|
　　 ||ACはこちらへ|
　　 ||　　　　  　|
　　 ||￣￣￣￣￣￣ 
∧_∧||
(`･ω･||
（ つ||０
　uｰu*/
#include <bits/stdc++.h>
using namespace std;
//output and debug
template <class T> using V = vector<T>;
template <class T, class U> 
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}
template <class T> ostream& operator<<(ostream& os,const V<T>& v) {
    os << "[";
    bool f = false;
    for (auto d : v) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "]";
}
template <class T> ostream& operator<<(ostream& os,const set<T>& s) {
    os << "{";
    bool f = false;
    for (auto d : s) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "}";
}
template <class T> ostream& operator<<(ostream& os, const multiset<T>& s) {
    os << "{";
    bool f = false;
    for (auto d : s) {
        if (f) os << ", ";
        f = true;
        os << d;
    }
    return os << "}";
}
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& s) {
    os << "{";
    bool f = false;
    for (auto p : s) {
        if (f) os << ", ";
        f = true;
        os << p.first << ": " << p.second;
    }
    return os << "}";
}
template<class T, class... Ts>
void o(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}
#ifdef LOCAL
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        o(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif
// input
template<class... T>
void in(T&... a){
    (cin >> ... >> a);
}
template<class T> void in(vector<T>& a){ for(auto&& i : a) in(i); }
template<class T, class L> void in(pair<T, L>& p){ in(p.first); in(p.second); }
template<class T> void in(T& a){ cin >> a; }
#define rep1(n)          for(ll i = 0; i < n; ++i)
#define rep2(i, n)       for(ll i = 0; i < n; ++i)
#define rep3(i, j, n)    for(ll i = j; i < n; ++i)
#define overload3(a, b, c,  e, ...) e
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i,n) for(ll i = n-1;i>=0;--i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using ll = long long ;
using ld = long double;
using pa = pair<ll,ll>;
using t2 = tuple<ll,ll>;
using tu = tuple<ll,ll,ll>;
using vi = vector<ll>;
using vs = vector<string>;
using vp = vector<pa>;
using vvi = vector<vi>;
using vvp = vector<vp>;
using vvvi = vector<vvi>;
using v4 = vector<vvvi>;
using vt = vector<tu>;
const ll INF = (1ll << 29);
const ll inf = INF*INF;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
void Yes(bool i = true){ return o(i?"Yes":"No"); }
//reversed priority_queue
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
const ll mod = 998244353;
//const ll mod = 1000000007;
int main(){
    ll n,m,x;
    cin >> n >> m >> x;
    vi dist(n,inf);
    vvp g(n);
    rep(i,m){
        ll u,v,c,t;
        cin >> u >> v >> c >> t;
        --u; --v;
        c += x*t;
        g[u].push_back(pa(c,v));
        g[v].push_back(pa(c,u));
    }
    auto daik = [&](){
        priority_queue<tuple<ll,ll>,vector<tuple<ll,ll>>,greater<tuple<ll,ll>>> q;
        q.push({0,0});
        while(!q.empty()){
            ll v,vc;
            tie(vc,v) = q.top();
            q.pop();
            if(dist[v]<=vc) continue;
            dist[v] = vc;
            for(auto to:g[v]){
                auto u = to.second;
                auto uc = to.first;
                if(dist[u]<=vc+uc) continue;
                q.push({vc+uc,u});
            }
        }
        return;
    };
    daik();
    if(dist[n-1] == inf) cout << -1 << endl;
    else cout << (dist[n-1]+x-1)/x << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0