题目背景
发完了 (k) 张照片，佳佳却得到了一个坏消息：他的 (MM) 得病了！佳佳和大家一样焦急万分！治好 (MM) 的病只有一种办法，那就是传说中的 (0) 号药水 ……怎么样才能得到 (0) 号药水呢？你要知道佳佳的家境也不是很好，成本得足够低才行……
题目描述
得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去 买——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：
(1) 份 (A) 药水混合 (1) 份 (B) 药水就可以得到 (1) 份 (C) 药水。（至于为什么 (1+1=1)，因为……这是魔法世界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法书上所有的配置方法，现在要问的就是：
(1.) 最少花多少钱可以配制成功这种珍贵的药水；
(2.) 共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不同的）。假定初始时你手中并没有任何可以用的药水。
输入格式
第一行有一个整数 (N(N<=1000))，表示一共涉及到的药水总数。药水从 (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)。
Solution
非常巧妙的最短路问题，模型转化过程值得我们学习。
读完题目后，对于 “(A+B->C)” 的条件我们很容易想到连两条边 ((C->A),(C->B))，然后跑一次树形 (dp)，但是实际上不可行，因为可能存在环。
既然树形 (dp) 不可行，那么我们考虑最短路算法，并且第二问的最短路计数更加证实了正解做法。
当时考虑出来要用最短路算法，但是在连边和如何跑最短路上出现了问题，因为貌似有多个起点。
但是当我们从最短路算法本质上再来想一想，问题就迎刃而解了：
考虑一个药水 (C) 如何花费最小代价：
(1.) 直接到魔法商店购买；
(2.) 由 (A) 和 (B) 合成，且保证 (A) 和 (B) 的代价最小。
如果我们考虑 (C) 由谁合成((C<-A+B))，问题还是不好解决；但换个角度，我们考虑 (A) 和 (B) 能合成谁((A+B->C))，就好做多了。
为什么呢？如果考虑 (C<-A+B)，如果当前 (A) 或 (B) 不是最优的，那么算出来的 (C) 肯定不是最优的，造成了无用的计算，使得复杂度直接爆炸！
而如果我们开个数组 (vis[i]) 记录哪些药水已经得出了最小花费（记这样的药水为 (k)），每次取一个花费最小的 (k)，再枚举另一个已经得出最小花费的药水 (k')，如果它们能合成药水 (d)，那么 (d) 可能更新到最小值。
发现我们上述的过程类似于 (dijkstra) 算法，直接模拟即可，注意另开数组维护最短路条数。
Code
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
#define db double
using namespace std;
inline int read()
{
char ch=getchar();
int a=0,x=1;
while(ch<'0'||ch>'9')
{
if(ch=='-') x=-x;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
a=(a<<1)+(a<<3)+(ch^48);
ch=getchar();
}
return a*x;
}
const int N=1005;
int n,Edge;
int cost[N],vis[N],f[N][N];
ll cnt[N];
void Dijkstra()
{
for(int i=1;i<n;i++) //进行n-1轮松弛操作
{
int Min=1e9,u;
for(int j=1;j<=n;j++) //取一个得出最小花费的药水来更新别的药水
{
if(!vis[j]&&cost[j]<Min) //只取没进行过松弛操作的j,以免造成时间浪费
{
u=j;Min=cost[j];
}
}
vis[u]=1; //记录一下u点已经松弛过它的出边终点了
for(int v=1;v<=n;v++)
{
if(vis[v]&&f[u][v]) //找另外已经得出最小花费的药水(松弛过了其他点的药水)
{
int w=f[u][v]; //它们所能合成的药水
if(cost[w]==cost[u]+cost[v])//如果通过u和v合成的花费和原来一样
{
cnt[w]+=cnt[u]*cnt[v]; //方法又多了cnt[u]*cnt[v]种
}
else if(cost[w]>cost[u]+cost[v]) //如果花费更少
{
cost[w]=cost[u]+cost[v];//松弛成功
cnt[w]=cnt[u]*cnt[v]; //更新记录方案数
}
}
}
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++) cost[i]=read(); //每个药水从商店购买的初始花费
for(int i=1;i<=n;i++) cnt[i]=1ll; //记录最小花费方案数,初始化为1,表示从商店购买
int u,v,w;
while(cin>>u>>v>>w)
{
u++;v++;w++; //编号+1
f[u][v]=f[v][u]=w; //表示 u+v->w
}
Dijkstra();
printf("%d %lld
",cost[1],cnt[1]); //输出最小花费和方案数
return 0;
}