P1875 Jia Jia's magic potion
/problem/P1875
Question background
Send it\(k\)In the photo, Jia Jia got bad news: his MM is sick! Jia Jia is as anxious as everyone! There is only one way to cure MM's disease, and that is the legendary\(0\)No. 1 potion... How to get it\(0\)Where is the potion? You have to know that Jiajia’s family is not very good, and the cost must be low enough...
Question description
There are different situations where ab is the same and c is contrary to the meaning of the question. The question can still be done, but the data needs to be corrected.
There are two ways to get a potion: you can configure it yourself according to the instructions in the magic book, or you can buy it at the magic store - there is a supply of each potion, although it may be expensive. There are many such records in the Magic Book:
\(1\)Part A Potion Mix\(1\)Part B potion can be obtained\(1\)Part C potion. (As for why\(1 + 1 = 1\), because... this is the magic world) OK, now you know that you need to get some kind of potion, and also know the prices of all the potions that may be involved and all the configuration methods in the magic book. Now what you need to ask is:
-
How much does it cost to prepare this precious potion successfully;
-
How many different minimally expensive options are there (two feasible configuration options are considered different if any of the steps are different). Assume that at the beginning you don't have any potions to use.
Input format
There is an integer in the first line\(N\)（\(N \le 1000\)) indicates the total number of potions involved. Potion from\(0 \sim N-1\)Sequential number,\(0\)The potion is the final preparation potion.
The second line has\(N\)Integers, respectively represent\(0 \sim N-1\)The price of all potions in the Magic Store (all indicate\(1\)price).
The third line starts with three integers A, B, and C, representing\(1\)Part A Potion Mix\(1\)Part B potion can be obtained\(1\)Part C potion. Note that if a certain two specific potion can be combined into a new potion, the result will be unique. In other words, there will be no situation where A and B are the same but C are different in certain two lines.
The input ends with a blank line.
Output format
Output two integers separated by spaces, respectively, to obtain\(0\)The minimum cost of the potion and the number of plans that cost the least.
Ensure that the number of plans does not exceed\(2^{63} - 1\)。
Input and Output Sample #1
Enter #1
7
10 5 6 3 2 2 3
1 2 0
4 5 1
3 6 2
Output #1
10 3
Instructions/tips
Data range:
The price of each potion is\(\ge 1\)and\(\le 2.8\times 10^4\)。
Sample description:
The best solution is\(3\)Types are:
- Buy it directly\(0\)No. potion;
- purchase\(4\)No. potion,\(5\)Prepare the potion\(1\)No. of potion, buy it directly\(2\)No. of potion, then prepare it\(0\)No. potion;
- purchase\(4\)No. potion,\(5\)Prepare the potion\(1\)No. of potion, buy\(3\)No. potion,\(6\)Prepare the potion\(2\)No. of potion, then prepare it\(0\)No. potion.
//There is no fixed "source point" here. I can define a pair of numbers. The first dimension stores the cost of a bottle of potion, and the second dimension stores the number of this potion. I first pushed all {potentials, potion numbers} into the priority queue.
//Then update other potions based on this smallest "potential cost". Assuming that the potion here is a, here the edge is used to store the potion b that can react chemically with a, and use the edge to store the new potion c that can be obtained by a and b.
//If the cost of a and b adds <c, then I can update the minimum price of c as cost[a]+cost[b], and the number of schemes for c is: ans[c]=ans[a]*ans[b];
//If the cost of a and b combined ==c, then I update the number of solutions to c: ans[c]+=ans[a]*ans[b];
//Here I need to make sure that the cost of a and b is the smallest, so I can use the vis array to mark it. If a has been updated (i.e. vis[a]===1), then I don't need to use a + other potion-- to update the new potion
//If a is enumerating the out edge of a, that is, the potion b that can react chemically with a, if the price of b is not the smallest (vis[b]!=1), then there is no need for me to use b+a to update c...
//The cost here is very similar to the "distance" in the shortest circuit
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define PLL pair<long,long>
const int M=1e6+10;
const int N=1e3+10;
struct edge{
int v,w,ne;
};
edge e[M];
bool vis[N];
//cost[i] represents the minimum cost of potion i, ans[i] represents the number of plans to obtain the minimum cost of potion i.
LL cost[N],ans[N],n;
int idx,h[N],a,b,c;
priority_queue<PLL,vector<PLL>,greater<PLL> > q;
//Save the picture
void add(int a,int b,int c){
e[idx]={b,c,h[a]};
h[a]=idx++;
}
void dijkstra(){
while(()){
auto t=();();
//The current minimum cost
int u=;
//If a has been updated, then it will be meaningless to update a again...
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];~i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
//If b has not been updated, it is proved that the b potion is not the minimum price yet... Then it would be meaningless for me to use b+a to update c...
if(vis[v]==0) continue;
if(cost[w]>cost[u]+cost[v]){
cost[w]=cost[u]+cost[v];
ans[w]=ans[u]*ans[v];
//Update the minimum price of potion c
({cost[w],w});
}
else if(cost[w]==cost[u]+cost[v]){
ans[w]+=ans[u]*ans[v];
}
}
}
}
int main()
{
cin>>n;
fill(h,h+N,-1);
for(int i=0;i<n;i++){
cin>>cost[i];
//Initialize to 1 first, because there is at least one solution
ans[i]=1;
({cost[i],i});
}
while(cin>>a>>b>c){
add(a,b,c);
if (a == b) continue;
add(b,a,c);
}
dijkstra();
cout<<cost[0]<<' '<<ans[0]<<'\n';
return 0;
}