結果
問題 |
No.1449 新プロランド
|
ユーザー |
|
提出日時 | 2024-04-29 16:26:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,343 bytes |
コンパイル時間 | 4,639 ms |
コンパイル使用メモリ | 262,552 KB |
最終ジャッジ日時 | 2025-02-21 09:38:50 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 4 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using ld = long double; using mint = modint998244353; int main() { int N, M; cin >> N >> M; vector<vector<int>> g(N); map<pair<int, int>, int> edge; for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; g[a].push_back(b); g[b].push_back(a); edge[make_pair(a, b)] = c; } vector<int> t(N); for (int i = 0; i < N; i++) cin >> t[i]; vector<ll> dist(N, 1e18); dist[0] = t[0]; vector<ll> cost(N, 0); cost[0] = t[0]; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push(make_pair(t[0], 0)); //vector<bool> vis(N, false); //vis[0] = true; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); for (auto v: g[u]) { //if (vis[v]) continue; if (dist[v] > dist[u] + t[v] + edge[make_pair(min(u, v), max(u, v))] / cost[u]) { cost[v] = cost[u] + t[v]; dist[v] = dist[u] + t[v] + edge[make_pair(min(u, v), max(u, v))] / cost[u]; //vis[v] = true; pq.push(make_pair(dist[v], v)); } } } //for (int i = 0; i < N; i++) cout << cost[i] << " \n"[i == N - 1]; //for (int i = 0; i < N; i++) cout << dist[i] << " \n"[i == N - 1]; cout << dist[N - 1] << endl; return 0; }