Gnome Exchanges
National Olympiad — National round
Submission name: gnom.cpp
Problem summary
Each item type i can be bought for cᵢ; unlimited copies are available. A promotion consumes one item of each of two specified distinct types x,y and produces one item of type a. Promotions can be chained and reused. Find the minimum purchase cost needed to obtain one item of type 1.
Input
n m; n purchase prices; m triples a x y.
Output
The minimum achievable cost of one type-1 item.
Constraints
1 ≤ n ≤ 100,000; 0 ≤ m ≤ 120,000; 0 ≤ cᵢ ≤ 1,000,000; 1 ≤ a,x,y ≤ n; the three indices in each promotion are distinct.
Worked example
An independently prepared example for this explanation.
Input
3 1 20 3 4 1 2 3
Output
7
Solution analysis
- Initialize tentative costs with direct purchase prices and process them in a min-priority queue.
- For each promotion remember how many ingredient types have been finalized and their total finalized cost.
- Once both ingredients are finalized, relax the product cost with their sum.
Why it works
Any production tree costs the sum of its purchased leaves. Its root cost is no smaller than either ingredient’s nonnegative cost. Therefore the usual minimum-first label-setting argument applies: an unprocessed cheaper recipe would have ingredients finalized no later than its product. Zero-cost ties cause no problem because direct-purchase leaves ground every finite recipe.
Watch out. The two ingredients are consumed; sharing one physical item between two branches is not allowed. Ordinary single-edge shortest paths do not model a two-input recipe.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any production tree costs the sum of its purchased leaves. Its root cost is no smaller
// than either ingredient’s nonnegative cost.
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<tuple>
#include<functional>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<long long>d(n+1);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
for(int i=1;i<=n;i++){
cin>>d[i];
pq.push({d[i],i});
}
vector<int>to(m),pending(m,2);
vector<long long>sum(m);
vector<vector<int>>uses(n+1);
for(int j=0;j<m;j++){
int x,y;
cin>>to[j]>>x>>y;
uses[x].push_back(j);
uses[y].push_back(j);
}
vector<bool>done(n+1);
while(!pq.empty()){
auto[cost,v]=pq.top();
pq.pop();
if(done[v]||cost!=d[v]){
continue;
}
done[v]=true;
for(int r:uses[v]){
sum[r]+=cost;
if(--pending[r]==0&&sum[r]<d[to[r]]){
d[to[r]]=sum[r];
pq.push({d[to[r]],to[r]});
}
}
}
cout<<d[1]<<'\n';
}