45 lines
1.6 KiB
C++
45 lines
1.6 KiB
C++
// P1875 魔法药水。每个原料位置独立选择制法，交换配方书写顺序不重复计数。
|
|
// 当前原题提示同一对原料可能有不同产物，必须保存所有不同配方。
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
ll addSat(ll a, ll b) { return a > LLONG_MAX - b ? LLONG_MAX : a + b; }
|
|
ll mulSat(ll a, ll b) {
|
|
if (a == 0 || b == 0) return 0;
|
|
return a > LLONG_MAX / b ? LLONG_MAX : a * b;
|
|
}
|
|
struct Recipe { int a, b, c; };
|
|
int main() {
|
|
ios::sync_with_stdio(false); cin.tie(nullptr);
|
|
int n; if (!(cin >> n)) return 0;
|
|
vector<ll> d(n), ways(n, 1);
|
|
for (ll &x : d) cin >> x;
|
|
vector<Recipe> rec;
|
|
vector<vector<int>> incident(n);
|
|
unordered_set<ll> seen;
|
|
int a, b, c;
|
|
while (cin >> a >> b >> c) {
|
|
if (a > b) swap(a, b);
|
|
ll key = (1LL * a * n + b) * n + c;
|
|
if (!seen.insert(key).second) continue;
|
|
int id = (int)rec.size(); rec.push_back({a, b, c});
|
|
incident[a].push_back(id); incident[b].push_back(id);
|
|
}
|
|
vector<int> need(rec.size(), 2);
|
|
vector<bool> done(n, false);
|
|
for (int round = 0; round < n; ++round) {
|
|
int u = -1;
|
|
for (int i = 0; i < n; ++i)
|
|
if (!done[i] && (u == -1 || d[i] < d[u])) u = i;
|
|
done[u] = true;
|
|
for (int id : incident[u]) {
|
|
if (--need[id] != 0) continue;
|
|
auto [a, b, c] = rec[id];
|
|
ll nd = d[a] + d[b], cnt = mulSat(ways[a], ways[b]);
|
|
if (nd < d[c]) { d[c] = nd; ways[c] = cnt; }
|
|
else if (nd == d[c]) ways[c] = addSat(ways[c], cnt);
|
|
}
|
|
}
|
|
cout << d[0] << ' ' << ways[0] << '\n';
|
|
}
|