自动搬运

查看原文

来自洛谷，原作者为

	半仙胡小桃 **

搬运于2025-08-24 21:31:20，当前版本为作者最后更新于2017-08-05 11:29:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}