这道题目有点奇怪。
我交堆优化dijk，怎么样都A不掉，都只有10分。
检查了7个小时，重构过，依然不行。
然后放下尊严写邻接矩阵写堆优化，一遍A....
why？？？？
大致是这么做的：
每种药是一个点，假设a+b合成c，那么建一条a到c的边，边权为得到b的代价，建一条b到c的边，边权为得到a的代价。
思考，一开始的时候，每种药都可以通过购买得到，假设价格最小的药是x，那么得到x一定不能更优了。因为如果更优，一定是通过其他两种药混合而成，而x已经是价格最低的药了，因此x通过其他两种药相加不可能更优。
根据最短路的做法，我们可以用x更新其他药。但这里有个问题。
假设x和y合成z。
我们在这里只确定了x是最优的，并不能确定y是最优的；考虑到以后用y更新其他药的时候，也会有y和x合成z的操作，而那时，y是最优的，x也是最优的，他们合成z一定是最便宜的。
因此用x更新其他药的时候，假设x和y合成z，那么只有当y已经被访问过，才执行更新操作。
至于计算方案数，假设x和y合成z，那么z一共可以有x的方案数乘y的方案数种方案数。
#include<bits/stdc++.h>
#define ll long long
#define N 1010
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
int a[N][N],n,x,y,z,vis[N];
ll d[N],f[N];
template<typename qw>inline void rll(qw &x){
qw f=1;x=0;char c=getchar();
while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
x*=f;
}
int main(){
rll(n);
fsb(i,1,n)rll(d[i]),f[i]=1;
mem(a,255);
while(~scanf("%d",&x)){
rll(y);rll(z);x++;y++;z++;a[x][y]=a[y][x]=z;
}
mem(vis,0);
fsb(T,1,n-1){
int u=-1;
fsb(i,1,n)
u=((!vis[i])&&(u==-1||d[u]>d[i]))?i:u;
vis[u]=1;
fsb(i,1,n){
if((a[u][i]==-1)||(!vis[i])||d[i]+d[u]>d[a[u][i]])continue;
if(d[i]+d[u]==d[a[u][i]])
f[a[u][i]]+=f[i]*f[u];
if(d[i]+d[u]<d[a[u][i]]){
d[a[u][i]]=d[i]+d[u];
f[a[u][i]]=f[u]*f[i];
}
}
}
printf("%lld %lld\n",d[1],f[1]);
return 0;
}
代码其实有问题，不过数据比较水，没有出现x和x可以合成z的情况。如果这种情况合法，那么对方案数的贡献只有f(x)×(f(x)+1)/2。