3695: 魔药-【2014暑期训练】T6Day2T2
Description
魔药
【问题描述】
得到一种药水有两种方法：按照魔法书上的指导自己配置或者到魔法商店里去买。那里对于每种药水都有供应，虽然有可能价格很贵。
在魔法书上有很多这样的记载：1份A药水混合1份B药水就可以得到1份C药水。（至于为什么1+1=1，因为……这是魔法世界）
现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法书上所有的配置方法，现在要问的就是：
1.最少花多少钱可以配制成功这种珍贵的药水；
2.共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不同的）。
假定初始时你手中并没有任何可以用的药水。
【文件输入】
第一行有一个整数N，表示一共涉及到的药水总数。药水从0~N-1顺序编号，0号药水就是最终要配制的药水。
第二行有N个整数，分别表示从0~N-1顺序编号的所有药水在魔法商店的价格（都表示1份的价格）。
第三行开始，每行有3个整数A、B、C，表示1份A药水混合1份B药水就可以得到1份C药水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是说不会出现某两行的A、B相同但C不同的情况。
【文件输出】
输出两个用空格隔开的整数，分别表示得到0号药水的最小花费以及花费最少的方案的数。
【输入样例】
7
10 5 6 3 2 2 3
1 2 0
4 5 1
3 6 2
【输出样例】
10 3
【样例说明】
最优方案有3种，分别是：直接买0号药水；买4号药水、5号药水配制成1号药水，直接买2号药水，然后配制成0号药水；买4号药水、5号药水配制成1号药水，买3号药水、6号药水配制成2，然后配制成0
【数据规模】
对于100%的数据，n<=1000。HINT
解决这道题只需要一个最短路的算法。只不过这里要应用的是最短路算法的思想，而不是照抄。下面以利用Dijkstra算法的思想解此题为例来说明。
每次，我们可以从所有未确定最终价格的药水中选一个价格最低的，它的当前价格肯定就是最优价格（即它的最优价格已确定）。然后我们找所有的用这个药水作为原料之一可以配制成的药水，更新它们的当前价格。事实上，只有在两个原料的价格都标记为最终确定后才更新药水的当前价格。至于最优方案的种数也很好确定，只需在每次更新价格时区分小于和等于两种情况即可。
这道题是我原创的所有题目中最满意的。它提供了一种考察某种算法的新思路。也就是说：这道题考察了Dijkstra算法；但是要想做出这道题，仅仅会背出Dijkstra算法是不行的，你必须深刻理解Dijkstra算法的思想精髓（也就是每次贪心地取最小值然后将其值固定）。