luoguP1875 佳佳的魔法药水

题目

---

这道题目有点奇怪。

我交堆优化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。