#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()); } };
基本的にはベルマンフォードするだけだが、負辺の含まれ方が特殊なので、更新されない頂点集合を大雑把にはぶいてベルマンフォードすると間に合うという問題。
#include <vector> #include <string> #include <map> #include <set> #include <algorithm> #include <iostream> #include <cmath> #include <climits> #include <queue> #include <stack> #include <numeric> using namespace std; #define vector2(TYPE) vector<vector<TYPE> > #define vector2_cons(TYPE, A, B, DEFAULT) ((A), vector<TYPE>((B), (DEFAULT))) class FixedDiceGameDiv1 { public: vector<double> CalcPatterns(int a, int b) { vector2(double) dp vector2_cons(double, a + 1, 2550, 0); dp[0][0] = 1.0; for (int i = 1; i < dp.size(); ++i) { for (int j = 0; j < dp[0].size(); ++j) { for (int k = 1; k <= b; ++k) { if (j - k >= 0) dp[i][j] += dp[i - 1][j - k]; } } } return dp.back(); } double getExpectation(int a, int b, int c, int d) { double numer = 0, denomi = 0; vector<double> a_table = CalcPatterns(a, b); vector<double> b_table = CalcPatterns(c, d); for (int ia = 0; ia < a_table.size(); ++ia) { for (int jb = 0; jb < min<int>(ia, b_table.size()); ++jb) { numer += (double)ia * a_table[ia] * b_table[jb]; denomi += (double)a_table[ia] * b_table[jb]; } } if (numer == 0) return -1.0; return numer / denomi; } };
けたあふれにちゅうい