結果
問題 |
No.2739 Time is money
|
ユーザー |
|
提出日時 | 2024-04-20 16:25:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,443 bytes |
コンパイル時間 | 2,072 ms |
コンパイル使用メモリ | 179,856 KB |
実行使用メモリ | 18,304 KB |
最終ジャッジ日時 | 2024-10-12 12:13:40 |
合計ジャッジ時間 | 8,925 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 13 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; struct Edge { int to, cost, time; Edge(int t, int c, int ti) : to(t), cost(c), time(ti) {} }; int main() { int N, M, X; cin >> N >> M >> X; vector<vector<Edge>> graph(N); for (int i = 0; i < M; i++) { 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); } vector<int> dist(N, INF), money(N, 0); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[0] = 0; pq.emplace(0, 0); while (!pq.empty()) { int cost = pq.top().first; int curr = pq.top().second; pq.pop(); if (cost > dist[curr]) continue; for (Edge& e : graph[curr]) { int next_cost = cost + e.cost + e.time * X; int next_money = money[curr] + e.cost; if (next_cost < dist[e.to]) { dist[e.to] = next_cost; money[e.to] = next_money; pq.emplace(next_cost, e.to); } else if (next_cost == dist[e.to] && next_money < money[e.to]) { money[e.to] = next_money; pq.emplace(next_cost, e.to); } } } if (dist[N - 1] == INF) { cout << "-1" << endl; } else { cout << (dist[N - 1] + X - 1) / X << endl; } return 0; }