結果
問題 | No.1480 Many Complete Graphs |
ユーザー |
![]() |
提出日時 | 2021-04-16 21:58:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 2,300 bytes |
コンパイル時間 | 4,239 ms |
コンパイル使用メモリ | 258,880 KB |
最終ジャッジ日時 | 2025-01-20 19:51:39 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;#define rep(i,n)for (int i = 0; i < int(n); ++i)#define rrep(i,n)for (int i = int(n)-1; i >= 0; --i)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()template<class T> void chmax(T& a, const T& b) {a = max(a, b);}template<class T> void chmin(T& a, const T& b) {a = min(a, b);}using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;const unsigned long long INF = 1002003004005006007;template<class T>std::vector<unsigned long long> dijkstra(std::vector<std::vector<std::pair<int,T>>>& to, int s=0) {struct QueElem {int v;unsigned long long c;bool operator<(const QueElem a) const {return c > a.c;}QueElem(int v, unsigned long long c): v(v), c(c) {}};std::priority_queue<QueElem> q;std::vector<unsigned long long> dist(to.size(), INF);dist[s] = 0;q.emplace(s, 0);while(!q.empty()) {QueElem qe = q.top(); q.pop();int u = qe.v;unsigned long long c = qe.c;if (c > dist[u]) continue;for(auto vc: to[u]) {int v = vc.first;unsigned long long nc = c + vc.second;if (nc < dist[v]) {dist[v] = nc;q.emplace(v, nc);}}}return dist;}int main() {ios::sync_with_stdio(false);cin.tie(0);int n, m;cin >> n >> m;vector<vector<pair<int, ll>>> to(n + 2 * m);rep(i, m) {ll k, c;cin >> k >> c;VI s(k);rep(j, k) cin >> s[j];int ev = n + 2 * i, ov = n + 2 * i + 1;for(int u: s) {if (u & 1) {to[u - 1].emplace_back(ov, u / 2);to[ev].emplace_back(u - 1, c + u / 2 + 1);to[ov].emplace_back(u - 1, c + u / 2 + 1);} else {to[u - 1].emplace_back(ev, u / 2);to[ev].emplace_back(u - 1, c + u / 2);to[ov].emplace_back(u - 1, c + u / 2 + 1);}}}auto dist = dijkstra(to);ll ans = dist[n - 1];if (ans == INF) ans = -1;cout << ans << '\n';}