結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
![]() |
提出日時 | 2023-12-02 17:46:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 458 ms / 2,000 ms |
コード長 | 8,447 bytes |
コンパイル時間 | 4,382 ms |
コンパイル使用メモリ | 265,732 KB |
最終ジャッジ日時 | 2025-02-18 06:02:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>typedef long long int ll;typedef long double ld;using namespace std;using namespace atcoder;template <typename T>struct edge {int src, to;T cost;edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}edge &operator=(const int &x) {to = x;return *this;}operator int() const { return to; }};template <typename T>using Edges = vector<edge<T>>;template <typename T>using WeightedGraph = vector<Edges<T>>;using UnweightedGraph = vector<vector<int>>;// Input of (Unweighted) GraphUnweightedGraph graph(int N, int M = -1, bool is_directed = false,bool is_1origin = true) {UnweightedGraph g(N);if (M == -1) M = N - 1;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;if (is_1origin) x--, y--;g[x].push_back(y);if (!is_directed) g[y].push_back(x);}return g;}// Input of Weighted Graphtemplate <typename T>WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,bool is_1origin = true) {WeightedGraph<T> g(N);if (M == -1) M = N - 1;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;cin >> c;if (is_1origin) x--, y--;g[x].emplace_back(x, y, c);if (!is_directed) g[y].emplace_back(y, x, c);}return g;}// Input of Edgestemplate <typename T>Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {Edges<T> es;for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;if (is_weighted)cin >> c;elsec = 1;if (is_1origin) x--, y--;es.emplace_back(x, y, c);}return es;}// Input of Adjacency Matrixtemplate <typename T>vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,bool is_directed = false, bool is_1origin = true) {vector<vector<T>> d(N, vector<T>(N, INF));for (int _ = 0; _ < M; _++) {int x, y;cin >> x >> y;T c;if (is_weighted)cin >> c;elsec = 1;if (is_1origin) x--, y--;d[x][y] = c;if (!is_directed) d[y][x] = c;}return d;}// 一般のグラフのstからの距離!!!!// unvisited nodes : d = -1vector<int> Depth(const UnweightedGraph &g, int start = 0) {int n = g.size();vector<int> ds(n, -1);ds[start] = 0;queue<int> q;q.push(start);while (!q.empty()) {int c = q.front();q.pop();int dc = ds[c];for (auto &d : g[c]) {if (ds[d] == -1) {ds[d] = dc + 1;q.push(d);}}}return ds;}// Depth of Rooted Weighted Tree// unvisited nodes : d = -1template <typename T>vector<T> Depth(const WeightedGraph<T> &g, int start = 0) {vector<T> d(g.size(), -1);auto dfs = [&](auto rec, int cur, T val, int par = -1) -> void {d[cur] = val;for (auto &dst : g[cur]) {if (dst == par) continue;rec(rec, dst, val + dst.cost, cur);}};dfs(dfs, start, 0);return d;}// Diameter of Tree// return value : { {u, v}, length }pair<pair<int, int>, int> Diameter(const UnweightedGraph &g) {auto d = Depth(g, 0);int u = max_element(begin(d), end(d)) - begin(d);d = Depth(g, u);int v = max_element(begin(d), end(d)) - begin(d);return make_pair(make_pair(u, v), d[v]);}// Diameter of Weighted Tree// return value : { {u, v}, length }template <typename T>pair<pair<int, int>, T> Diameter(const WeightedGraph<T> &g) {auto d = Depth(g, 0);int u = max_element(begin(d), end(d)) - begin(d);d = Depth(g, u);int v = max_element(begin(d), end(d)) - begin(d);return make_pair(make_pair(u, v), d[v]);}// nodes on the path u-v ( O(N) )template <typename G>vector<int> Path(G &g, int u, int v) {vector<int> ret;int end = 0;auto dfs = [&](auto rec, int cur, int par = -1) -> void {ret.push_back(cur);if (cur == v) {end = 1;return;}for (int dst : g[cur]) {if (dst == par) continue;rec(rec, dst, cur);if (end) return;}if (end) return;ret.pop_back();};dfs(dfs, u);return ret;}template <typename T>vector<T> dijkstra(WeightedGraph<T> &g, int start = 0) {using P = pair<T, int>;int N = (int)g.size();vector<T> d(N, T(-1));priority_queue<P, vector<P>, greater<P> > Q;d[start] = 0;Q.emplace(0, start);while (!Q.empty()) {P p = Q.top();Q.pop();int cur = p.second;if (d[cur] < p.first) continue;for (auto dst : g[cur]) {if (d[dst] == T(-1) || d[cur] + dst.cost < d[dst]) {d[dst] = d[cur] + dst.cost;Q.emplace(d[dst], dst);}}}return d;}// Nyaanさんのグラフ構造体// edge<T> 型Tの重みが付いた辺// Edges<T> 型Tの重みが付いた辺のリスト// WeightedGraph<T> 型Tの重みが付いた(有向/無向)グラフ// UnweightedGraph 重みなし(有向/無向)グラフ// graph(N, M(-1の時N-1), bool is_directed = false, bool is_1origin = true)// 重みなしのグラフを標準入力から読み込み、UnweightedGraph型で返す。// ex) graph(n,,,) であればN頂点の無向木// wgraph<T>(,,,) = 重みつきグラフ// esgraph,adjgraph = 隣接リスト,隣接行列を返す// - 機能 - ( だいたいO(N) )// vector<int> Depth(UnweightedGraph g, int s = 0)// sからの最短距離// vector<T> Depth(weightedGraph<T> g, int s = 0)// (重み付き根つき木(無向でも可だが遅くなる)) sからの距離// pair<pair<int, int>, int> Diameter(UnweightedGraph g)// pair<pair<int, int>, T> Diameter<T>(WeightedGraph<T> g)// 木の直径の両端,長さを返す// vector<int> Path<UnweightedGraph>(G &g, int u, int v)// vector<int> Path<WeightedGraph>(G &g, int u, int v)// (両端含む)パスの頂点列を返す// vector<T> dijkstra(g, s = 0)// ダイクストラ法 (O(ElogV))// 計算量:O(ElogV)// 届かなかったら-1#define inf 1010000000#define llinf 1001000000000000000ll#define pi 3.141592653589793238#define rep(i, n) for(ll i = 0; i < (n); i++)#define rep1(i, n) for(ll i = 1; i <= (n); i++)#define rep2(i,l,r) for(ll i = (l); i < (r); i++)#define per(i, n) for(ll i = (n)-1; i >= 0; i--)#define each(x, v) for (auto&& x : v)#define rng(a) a.begin(),a.end()#define fi first#define se second#define pb push_back#define eb emplace_back#define pob pop_back#define st string#define pcnt __builtin_popcountll#define bit(n) (1LL<<(n))template <class T = ll>inline T in(){ T x; cin >> x; return (x);}#define vcin(x,n) {for(ll loop=0; loop<(n); loop++) cin>>x[loop];}#define ret(x) { cout<<(x)<<endl;}#define rets(x) { cout<<(x)<< " ";}#define dame { ret("-1"); return 0;}#define yes { ret("Yes"); return 0;}#define no { ret("No"); return 0;}#define Endl cout<<endl;#define dump(x) { cout << #x << " = " << (x) << endl;}template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false;}template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false;}// 仮マクロ 便利だったら昇格#define unique(v) v.erase( unique(v.begin(), v.end()), v.end())// ここまで仮マクロ// clock()/CLOCKS_PER_SEC 秒数を知りたいときに用いる#define mod 998244353using mint = modint998244353;/*#define mod 1000000007using mint = modint1000000007;*/vector<ll> dx={1,0,-1,0};vector<ll> dy={0,1,0,-1};using pl = pair<ll,ll>;using ppl = pair<pl,ll>;// G.assign(n, vector<ll>()); グローバル変数にGを置く時に置く// 関数を置くのはここ以下int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(20);ll n,m; cin >> n >> m;auto g = wgraph<ll>(n,m,true);vector<ll> v1 = dijkstra(g,n-2), v2 = dijkstra(g,n-1);ll d1 = llinf, d2 = llinf;if(v1[n-1]!=-1) d1 = v1[n-1];if(v2[n-2]!=-1) d2 = v2[n-2];WeightedGraph<ll> g2(n);rep(i,n){each(x,g[i]){g2[x.to].eb(i,x.cost);}}vector<ll> v3 = dijkstra(g2,n-2), v4 = dijkstra(g2,n-1);rep(i,n-2){ll ans = llinf;if(v3[i] != -1 && v2[i] != -1 && d1 != llinf){chmin(ans,v3[i]+v2[i]+d1);}if(v4[i] != -1 && v1[i] != -1 && d2 != llinf){chmin(ans,v4[i]+v1[i]+d2);}if(ans==llinf) ans = -1;ret(ans)}}