結果
| 問題 |
No.30 たこやき工場
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-06-18 20:14:15 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 5,000 ms |
| コード長 | 8,932 bytes |
| コンパイル時間 | 2,243 ms |
| コンパイル使用メモリ | 180,976 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-12-21 05:26:22 |
| 合計ジャッジ時間 | 2,591 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
#include <bits/stdc++.h>
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define RFOR(i, a, b) for (ll i = (b)-1; i >= (a); i--)
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep1(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define pii pair<int, int>
#define vi vector<int>
using namespace std;
template <class S, class T>
ostream& operator<<(ostream& o, const pair<S, T>& p)
{
return o << "(" << p.first << "," << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& vc)
{
o << "sz = " << vc.size() << endl
<< "[";
for (const T& v : vc)
o << v << ",";
o << "]";
return o;
}
using ll = long long;
constexpr ll MOD = 1000000007;
template <typename T>
struct Edge {
Edge(const std::size_t from_, const std::size_t to_, const T cost_) : from{from_}, to{to_}, cost{cost_} {}
Edge<T>& operator=(const Edge<T>&) = default;
std::size_t from;
std::size_t to;
T cost;
bool operator<(const Edge<T>& e) const //inverse
{
return cost != e.cost ? cost > e.cost : to < e.to;
}
};
template <typename T>
class Graph
{
public:
Graph(const std::size_t v) : m_v{v}, m_e{0}
{
m_table.resize(v);
m_reversed_table.resize(v);
}
void addEdge(const std::size_t from, const std::size_t to, const T cost)
{
m_e++;
m_table[from].push_back(Edge<T>{from, to, cost});
m_reversed_table[to].push_back(Edge<T>{to, from, cost});
}
void TopologocalSort(std::vector<std::size_t>& srt) const
{
srt.clear();
std::vector<bool> used(m_v, false);
for (std::size_t i = 0; i < m_v; i++) {
dfs_topo(i, used, srt);
}
std::reverse(srt.begin(), srt.end());
}
std::size_t SCC(std::vector<std::size_t>& cmp) const
{
assert(cmp.size() == m_v);
for (std::size_t i = 0; i < m_v; i++) {
cmp[i] = 0;
}
std::vector<std::size_t> st;
std::vector<bool> used(m_v, false);
for (std::size_t i = 0; i < m_v; i++) {
if (not used[i]) {
dfs1_scc(i, st, used);
}
}
for (std::size_t i = 0; i < m_v; i++) {
used[i] = false;
}
std::size_t comp = 0;
for (std::size_t i = 0; i < st.size(); i++) {
const std::size_t s = st[st.size() - i - 1];
if (not used[s]) {
dfs2_scc(s, comp++, cmp, used);
}
}
return comp;
}
bool BellmanFord(const std::size_t s, std::vector<T>& d) const
{
assert(s < m_v);
assert(d.size() == m_v);
for (std::size_t i = 0; i < m_v; i++) {
d[i] = INF;
}
d[s] = 0;
bool no_negative_loop = true;
for (std::size_t i = 0; i < m_v; i++) {
for (std::size_t v = 0; v < m_v; v++) {
if (d[v] != INF) {
for (const auto& e : m_table[v]) {
if (d[e.to] > d[e.from] + e.cost) {
d[e.to] = d[v] + e.cost;
if (i == m_v - 1) {
d[e.to] = -INF; // Confirm " -INF < min(possible_cost) * V "
no_negative_loop = false;
}
}
}
}
}
}
return no_negative_loop;
}
void Dijkstra(const std::size_t s, std::vector<T>& d) const
{
assert(s < m_v);
assert(d.size() == m_v);
using P = std::pair<T, std::size_t>;
std::priority_queue<P, std::vector<P>, std::greater<P>> q;
for (std::size_t i = 0; i < m_v; i++) {
d[i] = INF;
}
d[s] = 0;
q.push(std::make_pair(0, s));
while (not q.empty()) {
const P& p = q.top();
const T cost = p.first;
const std::size_t v = p.second;
q.pop();
if (d[v] < cost) {
continue;
}
for (const auto& e : m_table[v]) {
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
q.push(std::make_pair(d[e.to], e.to));
}
}
}
}
void WarshallFloyd(std::vector<std::vector<T>>& d) const
{
assert(d.size() == m_v);
for (std::size_t i = 0; i < m_v; i++) {
assert(d[i].size() == m_v);
for (std::size_t j = 0; j < m_v; j++) {
if (i == j) {
d[i][j] = 0;
} else {
d[i][j] = INF;
}
}
for (const auto& e : m_table[i]) {
d[i][e.to] = std::min(e.cost, d[i][e.to]); // For doubled-link
}
}
for (std::size_t k = 0; k < m_v; k++) {
for (std::size_t i = 0; i < m_v; i++) {
for (std::size_t j = 0; j < m_v; j++) {
if (d[i][j] > d[i][k] + d[k][j] and d[i][k] < INF and d[k][j] < INF) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
void restorePath(const std::size_t s, const std::size_t t, const std::vector<T>& d, std::vector<std::size_t>& path) const
{
assert(s < m_v);
assert(t < m_v);
assert(d.size() == m_v);
path.clear();
std::size_t pos = t;
path.push_back(t);
while (pos != s) {
for (const auto& e : m_reversed_table[pos]) {
if (d[e.to] + e.cost == d[pos]) {
pos = e.to;
break;
}
}
path.push_back(pos);
}
std::reverse(path.begin(), path.end());
}
std::size_t getV() const
{
return m_v;
}
std::size_t getE() const
{
return m_e;
}
const std::vector<std::vector<Edge<T>>>& getEdge() const
{
return m_table;
}
std::vector<std::vector<Edge<T>>>& getEdge()
{
return m_table;
}
const std::vector<std::vector<std::size_t>>& getReversedEdge() const
{
return m_reversed_table;
}
std::vector<std::vector<std::size_t>>& getReversedEdge()
{
return m_reversed_table;
}
static constexpr T INF = std::numeric_limits<T>::max() / 100;
private:
void dfs_topo(const std::size_t s, std::vector<bool>& used, std::vector<std::size_t>& srt) const
{
assert(s < m_v);
assert(used.size() == m_v);
if (not used[s]) {
used[s] = true;
for (const auto& e : m_table[s]) {
dfs_topo(e.to, used, srt);
}
srt.push_back(s);
}
}
void dfs1_scc(const std::size_t s, std::vector<std::size_t>& st, std::vector<bool>& used) const
{
assert(s < m_v);
assert(used.size() == m_v);
used[s] = true;
for (const auto& e : m_table[s]) {
if (not used[e.to]) {
dfs1_scc(e.to, st, used);
}
}
st.push_back(s);
}
void dfs2_scc(const std::size_t s, const std::size_t index, std::vector<std::size_t>& cmp, std::vector<bool>& used) const
{
assert(s < m_v);
assert(index < m_v);
assert(cmp.size() == m_v);
cmp[s] = index;
used[s] = true;
for (const auto& e : m_reversed_table[s]) {
if (not used[e.to]) {
dfs2_scc(e.to, index, cmp, used);
}
}
};
const std::size_t m_v;
std::size_t m_e;
std::vector<std::vector<Edge<T>>> m_table;
std::vector<std::vector<Edge<T>>> m_reversed_table;
};
int main()
{
std::size_t N;
std::size_t M;
cin >> N >> M;
Graph<std::size_t> g(N);
Graph<std::size_t> revg(N);
rep(i, M)
{
std::size_t p, q, r;
cin >> p >> q >> r;
p--, r--;
g.addEdge(p, r, q);
revg.addEdge(r, p, q);
}
vector<int> isleaf(N, false);
vector<int> dp(N, 0);
rep(i, N)
{
if (revg.getEdge()[i].empty()) {
isleaf[i] = true;
}
}
vector<std::size_t> srt(N);
g.TopologocalSort(srt);
//show(srt);
dp[N - 1] = 1;
for (int i = N - 1; i >= 0; i--) {
for (const auto& e : revg.getEdge()[srt[i]]) {
dp[e.to] += dp[srt[i]] * e.cost;
}
}
for (int i = 0; i < N - 1; i++) {
if (isleaf[i]) {
cout << dp[i] << endl;
} else {
cout << 0 << endl;
}
}
return 0;
}