#966483 (C++17) No.2712 Play more!

提出ソース

結果

問題	No.2712 Play more!
ユーザー	ei1333333
提出日時	2024-03-31 13:43:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	450 ms / 2,000 ms
コード長	5,841 bytes
コンパイル時間	2,235 ms
コンパイル使用メモリ	214,208 KB
実行使用メモリ	6,548 KB
最終ジャッジ日時	2024-04-03 12:08:54
合計ジャッジ時間	6,160 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	1 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	2 ms 6,548 KB
testcase_07	AC	151 ms 6,548 KB
testcase_08	AC	149 ms 6,548 KB
testcase_09	AC	151 ms 6,548 KB
testcase_10	AC	2 ms 6,548 KB
testcase_11	AC	85 ms 6,548 KB
testcase_12	AC	388 ms 6,548 KB
testcase_13	AC	51 ms 6,548 KB
testcase_14	AC	235 ms 6,548 KB
testcase_15	AC	450 ms 6,548 KB
testcase_16	AC	29 ms 6,548 KB
testcase_17	AC	7 ms 6,548 KB
testcase_18	AC	50 ms 6,548 KB
testcase_19	AC	16 ms 6,548 KB
testcase_20	AC	95 ms 6,548 KB
testcase_21	AC	39 ms 6,548 KB
testcase_22	AC	347 ms 6,548 KB
testcase_23	AC	12 ms 6,548 KB
testcase_24	AC	48 ms 6,548 KB
testcase_25	AC	7 ms 6,548 KB
testcase_26	AC	60 ms 6,548 KB
testcase_27	AC	66 ms 6,548 KB
testcase_28	AC	9 ms 6,548 KB
testcase_29	AC	50 ms 6,548 KB
testcase_30	AC	394 ms 6,548 KB
testcase_31	AC	4 ms 6,548 KB
testcase_32	AC	4 ms 6,548 KB
testcase_33	AC	2 ms 6,548 KB
testcase_34	AC	2 ms 6,548 KB
testcase_35	AC	2 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "template/template.hpp"
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  explicit FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}
#line 2 "shortest-path/bellman-ford.hpp"



#line 2 "graph/graph-template.hpp"

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) Graph
UnweightedGraph 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 Graph
template <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 Edges
template <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;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <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;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 6 "shortest-path/bellman-ford.hpp"

// bellman-ford法
// goalが存在しないとき-> 負閉路が存在するときは空列を返す
// goalが存在するとき  -> startとgoalの間に負閉路が存在する時に負閉路を返す
template <typename T>
vector<T> bellman_ford(int N, Edges<T> &es, int start = 0, int goal = -1) {
  T INF = numeric_limits<T>::max() / 2;
  vector<T> d(N, INF);
  d[start] = 0;
  for (int i = 0; i < N; i++) {
    bool update = false;
    for (auto &e : es) {
      if (d[e.src] == INF) continue;
      if (d[e.to] > d[e.src] + e.cost) {
        update = true, d[e.to] = d[e.src] + e.cost;
      }
    }
    if (!update) return d;
  }

  if (goal == -1) return vector<T>();
  vector<bool> negative(N, false);
  for (int i = 0; i < N; i++) {
    for (auto &e : es) {
      if (d[e.src] == INF) continue;
      if (d[e.to] > d[e.src] + e.cost)
        negative[e.to] = true, d[e.to] = d[e.src] + e.cost;
      if (negative[e.src] == true) negative[e.to] = true;
    }
  }

  if (negative[goal] == true)
    return vector<T>();
  else
    return d;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector< int > A(N);
  cin >> A;
  Edges< int64 > es;
  for(int i = 0; i < N; i++) {
    es.emplace_back(i, i + N, -A[i]);
  }
  for(int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    es.emplace_back(a + N, b, c);
  }
  auto ret = bellman_ford(N + N, es, 0, N + N - 1);
  if(ret.empty()) cout << "inf" << endl;
  else cout << -ret.back() << endl;
}

yukicoder

結果

テストケース

ソースコード