結果
問題 | No.2739 Time is money |
ユーザー | butsurizuki |
提出日時 | 2024-04-21 02:48:35 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 306 ms / 2,000 ms |
コード長 | 1,038 bytes |
コンパイル時間 | 3,850 ms |
コンパイル使用メモリ | 284,240 KB |
実行使用メモリ | 20,612 KB |
最終ジャッジ日時 | 2024-04-21 02:48:47 |
合計ジャッジ時間 | 8,840 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 81 ms
13,568 KB |
testcase_03 | AC | 224 ms
17,568 KB |
testcase_04 | AC | 123 ms
12,928 KB |
testcase_05 | AC | 130 ms
13,056 KB |
testcase_06 | AC | 155 ms
15,952 KB |
testcase_07 | AC | 264 ms
19,852 KB |
testcase_08 | AC | 285 ms
20,108 KB |
testcase_09 | AC | 306 ms
20,344 KB |
testcase_10 | AC | 171 ms
19,620 KB |
testcase_11 | AC | 261 ms
20,200 KB |
testcase_12 | AC | 189 ms
18,944 KB |
testcase_13 | AC | 188 ms
18,784 KB |
testcase_14 | AC | 178 ms
18,992 KB |
testcase_15 | AC | 120 ms
17,804 KB |
testcase_16 | AC | 111 ms
16,820 KB |
testcase_17 | AC | 272 ms
20,612 KB |
testcase_18 | AC | 288 ms
20,524 KB |
testcase_19 | AC | 130 ms
17,800 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using pl=pair<long long,long long>; using Graph=vector<vector<pl>>; vector<long long> dijkstra(long long v,long long n,Graph &g){ vector<long long> d(n,8e18); priority_queue<pl,vector<pl>,greater<pl>> pq; d[v]=0; pq.push({0,v}); while(!pq.empty()){ pl od=pq.top();pq.pop(); if(d[od.second]!=od.first){continue;} for(auto &nx : g[od.second]){ if(d[nx.first]>od.first+nx.second){ d[nx.first]=od.first+nx.second; pq.push({d[nx.first],nx.first}); } } } return d; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long n,m,x; cin >> n >> m >> x; Graph g(n); for(long long i=0;i<m;i++){ long long u,v,c,t; cin >> u >> v >> c >> t; u--;v--; g[u].push_back({v,t*x+c}); g[v].push_back({u,t*x+c}); } vector<long long> d=dijkstra(0,n,g); // for(auto &nx : d){cout << nx << " ";}cout << "\n"; if(d[n-1]>4e18){cout << "-1\n";} else{ cout << (d[n-1]+x-1)/x << "\n"; } return 0; }