結果

問題 No.2739 Time is money
ユーザー iroha HEFFERNANiroha HEFFERNAN
提出日時 2024-04-21 12:45:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 379 ms / 2,000 ms
コード長 3,933 bytes
コンパイル時間 2,642 ms
コンパイル使用メモリ 208,108 KB
実行使用メモリ 21,120 KB
最終ジャッジ日時 2024-04-21 12:45:27
合計ジャッジ時間 9,423 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 184 ms
13,440 KB
testcase_03 AC 284 ms
17,540 KB
testcase_04 AC 155 ms
13,056 KB
testcase_05 AC 207 ms
13,592 KB
testcase_06 AC 290 ms
17,092 KB
testcase_07 AC 379 ms
19,968 KB
testcase_08 AC 357 ms
20,352 KB
testcase_09 AC 363 ms
20,352 KB
testcase_10 AC 320 ms
19,712 KB
testcase_11 AC 355 ms
20,352 KB
testcase_12 AC 284 ms
18,688 KB
testcase_13 AC 280 ms
18,688 KB
testcase_14 AC 272 ms
18,816 KB
testcase_15 AC 233 ms
18,180 KB
testcase_16 AC 221 ms
16,920 KB
testcase_17 AC 319 ms
21,112 KB
testcase_18 AC 352 ms
21,120 KB
testcase_19 AC 296 ms
17,792 KB
権限があれば一括ダウンロードができます

ソースコード

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