<commit_before>#pragma once

#include "Graph.hpp"

template <typename Weight>
pair<bool,Array<Weight>> spfa(const Graph<Weight> &g, int s) {
  const int n = g.size();
  const Weight INF = 1e9;
  Array<Weight> d(n, INF); d[s] = 0;
  vector<int> updated(n, 0);
  vector<bool> inque(n, false);
  queue<int> que;
  que.push(s);
  while (!que.empty()) {
    int from = que.front();
    que.pop();
    inque[from] = false;
    ++updated[from];
    if (updated[from] == n+1) return {false, d}; // negative cycle
    for (auto e: g[from]) {
      Weight cost = d[from] + e.cost;
      if (cost < d[e.to]) {
        d[e.to] = cost;
        if (!inque[e.to]) {
          que.push(e.to);
          inque[e.to] = true;
        }
      }
    }
  }
  return {true, d};
}

// Verified : AOJ GRL_1_A (Single Source Shortest Path)
/*
int main() {
  int V, E, r, s, t, d;
  cin >> V >> E >> r;
  Graph<int> g(V);
  while (E--) {
    cin >> s >> t >> d;
    add_edge(g, s, t, d);
  }
  const int INF = 1e9;
  Array<int> res = spfa(g, r).second;
  for (int i = 0; i < V; ++i) {
    if (res[i] == INF) cout << "INF" << endl;
    else cout << res[i] << endl;
  }
  return 0;
}
*/

// Verified : AOJ GRL_1_B (Single Source Shortest Path (Negative Edges))
/*
int main() {
  int V, E, r, s, t, d;
  cin >> V >> E >> r;
  Graph<int> g(V);
  while (E--) {
    cin >> s >> t >> d;
    add_edge(g, s, t, d);
  }
  const int INF = 1e9;
  bool flag;
  Array<int> res;
  tie(flag, res) = spfa(g, r);
  if (flag) {
    for (int i = 0; i < V; ++i) {
      if (res[i] == INF) cout << "INF" << endl;
      else cout << res[i] << endl;
    }
  }
  else {
    cout << "NEGATIVE CYCLE" << endl;
  }
  return 0;
}
*/<commit_msg>modify spfa<commit_after>#pragma once

#include "Graph.hpp"

template <typename Cost>
pair<bool,vector<Cost>> spfa(const CGraph<Cost> &g, int s, Cost inf, Cost zero = 0) {
  const int n = g.size();
  vector<Cost> d(n, inf); d[s] = zero;
  vector<int> updated(n, 0);
  vector<bool> inque(n, false);
  queue<int> que;
  que.push(s);
  while (!que.empty()) {
    int from = que.front();
    que.pop();
    inque[from] = false;
    ++updated[from];
    if (updated[from] == n+1) return {false, d}; // negative cycle
    for (auto e: g[from]) {
      Cost cost = d[from] + e.cost;
      if (cost < d[e.to]) {
        d[e.to] = cost;
        if (!inque[e.to]) {
          que.push(e.to);
          inque[e.to] = true;
        }
      }
    }
  }
  return {true, d};
}

// Verified : AOJ GRL_1_A (Single Source Shortest Path)
/*
int main() {
  int V, E, r, s, t, d;
  cin >> V >> E >> r;
  CGraph<int> g(V);
  while (E--) {
    cin >> s >> t >> d;
    add_edge(g, s, t, d);
  }
  const int INF = 1e9;
  auto res = spfa(g, r, INF).second;
  for (int i = 0; i < V; ++i) {
    if (res[i] == INF) cout << "INF" << endl;
    else cout << res[i] << endl;
  }
  return 0;
}
*/

// Verified : AOJ GRL_1_B (Single Source Shortest Path (Negative Edges))
/*
int main() {
  int V, E, r, s, t, d;
  cin >> V >> E >> r;
  CGraph<int> g(V);
  while (E--) {
    cin >> s >> t >> d;
    add_edge(g, s, t, d);
  }
  const int INF = 1e9;
  bool flag;
  vector<int> res;
  tie(flag, res) = spfa(g, r, INF);
  if (flag) {
    for (int i = 0; i < V; ++i) {
      if (res[i] == INF) cout << "INF" << endl;
      else cout << res[i] << endl;
    }
  }
  else {
    cout << "NEGATIVE CYCLE" << endl;
  }
  return 0;
}
*/
{'fraction_non_alphanumeric': 0.20586492890995262, 'fraction_numerical': 0.008293838862559242, 'mean_word_length': 2.2439961575408263, 'pattern_counts': {'":': 0, '<': 72, '<?xml version=': 0, '>': 74, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5856997', 'n_tokens_mistral': 1479, 'n_tokens_neox': 1451, 'n_words': 412}