Hatena::Grouptopcoder

peryaudoのTopCoder日記

2016-04-27

NegativeGraphDiv2

| 23:14

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
using ll = long long;

const ll INF = 1LL << 60LL;

class NegativeGraphDiv2 {
 public:
  long long findMin(int N, vector<int> s, vector<int> t, vector<int> weight, int charges) {
    vector<vector<pair<int, ll>>> edges(N);
    for (int i = 0; i < s.size(); ++i) {
      edges[s[i] - 1].emplace_back(t[i] - 1, (ll)weight[i]);
    }
    vector<vector<ll>> dist(N, vector<ll>(charges + 1, INF));
    dist[0][0] = 0;

    set<int> changed;
    changed.insert(0);

    while (!changed.empty()) {
      set<int> next_changed;
      for (int ch : changed) {
        for (int from = 0; from < N; ++from) {
          for (pair<int, ll> edge : edges[from]) {
            if (dist[edge.first][ch] > dist[from][ch] + edge.second) {
              dist[edge.first][ch] = dist[from][ch] + edge.second;
              next_changed.insert(ch);
            }
            if (ch + 1 <= charges && dist[edge.first][ch + 1] > dist[from][ch] - edge.second) {
              dist[edge.first][ch + 1] = dist[from][ch] - edge.second;
              next_changed.insert(ch);
              next_changed.insert(ch + 1);
            }
          }
        }
      }
      changed = next_changed;
    }
    return *min_element(dist.back().begin(), dist.back().end());
  }
};

基本的にはベルマンフォードするだけだが、負辺の含まれ方が特殊なので、更新されない頂点集合を大雑把にはぶいてベルマンフォードすると間に合うという問題。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/peryaudo/20160427