結果
問題 | No.2739 Time is money |
ユーザー | butsurizuki |
提出日時 | 2024-04-21 02:47:43 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,045 bytes |
コンパイル時間 | 3,919 ms |
コンパイル使用メモリ | 284,228 KB |
実行使用メモリ | 20,616 KB |
最終ジャッジ日時 | 2024-04-21 02:47:55 |
合計ジャッジ時間 | 9,336 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 78 ms
13,328 KB |
testcase_03 | AC | 157 ms
17,568 KB |
testcase_04 | AC | 81 ms
13,184 KB |
testcase_05 | AC | 117 ms
13,056 KB |
testcase_06 | AC | 155 ms
15,824 KB |
testcase_07 | AC | 233 ms
19,968 KB |
testcase_08 | AC | 220 ms
20,124 KB |
testcase_09 | AC | 221 ms
20,308 KB |
testcase_10 | AC | 172 ms
19,692 KB |
testcase_11 | AC | 249 ms
20,352 KB |
testcase_12 | AC | 171 ms
18,920 KB |
testcase_13 | AC | 154 ms
18,828 KB |
testcase_14 | AC | 144 ms
18,828 KB |
testcase_15 | AC | 107 ms
17,932 KB |
testcase_16 | AC | 109 ms
16,820 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | RE | - |
ソースコード
#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; 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; }