P1875 佳佳的魔法药水 (最短路,DP)

题目链接

Solution

好题. 一开始一直在想怎么蛇皮建图,但是发现一直蛇不出来...
正解是用类似于 dijkstra 的算法对所有点进行松弛.
对于每个元素记录两个值:

• (cost) 代表它的最小花费.
• (ans) 代表它的方案数.
• 同时用一个(f_{i,j})记录第(i)种和第(j)种药水可以合成第(f_{i,j})这种药水.

似乎可以发现我们存合并状态的数组很像临接矩阵?
然后就可以开始蛇了...

我们对于每一瓶药水,其 (cost) 初值为其直接买的花费.
(ans) 初值为 1.
每一次选择未松弛的价格最小的药水(u),然后对于所有的 (f_{u,i}) 值进行更新.

(1.) 如若 (cost_{f_{u,i}}>cost_u+cost_i)
那么 (cost_{f_{u,i}}=cost_u+cost_i),同时 (ans_{f_{u,i}}=ans_u*ans_i)

(2.) 如果 (cost_{f_{u,i}}=cost_u+cost_i)
那么 (ans_{f_{u,i}}=ans_{f_{u,i}}+ans_u*ans_i)

然后最后的答案即为 (cost[0])以及 (ans[0]).

Code

#include<bits/stdc++.h>
using namespace std;
const int inf=192608173;
const int maxn=1008;
int f[maxn][maxn],n;
int cost[maxn],ans[maxn];
 
void dijkstra()
{
  	int v[1010]={0},k,minimum;
  	for(int i=1;i<=n;i++)
  	{
    	minimum=inf;
    	for(int j=0;j<n;j++)
      	if(!v[j]&&cost[j]<minimum)
      	{k=j;minimum=cost[j];}
      	//类似于dij的选边进行松弛.
    	if(minimum==inf) break;
   	 	v[k]=1;
    	for(int j=0;j<n;j++)
      	if(v[j]&&f[j][k]>-1) 
        if(cost[f[j][k]]>cost[j]+cost[k]) 
        {
        	cost[f[j][k]]=cost[j]+cost[k];
        	ans[f[j][k]]=ans[j]*ans[k];
        	continue;
        }
        else if(cost[f[j][k]]==cost[j]+cost[k]) 
        ans[f[j][k]]+=ans[j]*ans[k];
  	}
}
 
int main()
{
	scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&cost[i]);
  	int a,b,c;
	memset(f,-1,sizeof(f));
 	while(cin>>a>>b>>c)
  	{f[a][b]=c;f[b][a]=c;}//此处建边.
 	for(int i=0;i<n;i++)
    ans[i]=1;
  	dijkstra();
  	cout<<cost[0]<<" "<<ans[0];
  	return 0;
}