题解 P1875 【佳佳的魔法药水】

· · 题解

QAQ

迪杰斯特拉算法

cost[i]表示获得i药水所需要的最小代价，f[i]表示i药水是否已经找到了最小花费，ans[i]表示i药水在当前最小花费的方案数，f[i][j]表示i药水与j药水能够合成的药水

类似于迪杰斯特拉，每次找一个值最小但却没有确定最小值的药水，将其标记为最小值，然后枚举能与此药水合成药水的药水，用找到的药水与配对的药水更新合成药水的最小值

至于方案数，有两种情况，

1：两个原料药水合成的药水的原本最小花费等于原料药水的总花费，那么合成药水的方案数就需要在原本的基础上加上两个原料药水方案的乘积

2：两个原料药水合成的药水的原本最小花费等于原料药水的总花费，那么合成药水的方案数就等于两个原料药水方案的乘积

然后输出就行了！

顺便吐槽一下，题目上没有数据范围，害我RE了一次！

#include <cstdio>
#include <iostream>
using namespace std;
int cost[9999],ans[9999];
int soc[3000][3000];
bool f[3000];
int main()
{
    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)
     scanf("%d",&cost[i]),ans[i]=1;
    int a,b,c; 
    while(scanf("%d%d%d",&a,&b,&c)!=EOF) 
     soc[a+1][b+1]=soc[b+1][a+1]=c+1;

    for(int i=1;i<n;i++)
     {
         int maxn=0x7fffffff;
         for(int j=1;j<=n;j++)
          if(!f[j]&&cost[j]<maxn) 
          b=j,maxn=cost[j];

        f[b]=1;

        for(int j=1;j<=n;j++)
        if(f[j]&&soc[b][j])
         {
             if(cost[b]+cost[j]==cost[soc[b][j]])
              ans[soc[b][j]]+=ans[b]*ans[j];
            if(cost[b]+cost[j]<cost[soc[b][j]]) 
             cost[soc[b][j]]=cost[b]+cost[j],ans[soc[b][j]]=ans[b]*ans[j];
         }
     }

     printf("%d %d",cost[1],ans[1]);

     return 0;
}