vijosP1285 佳佳的魔法药水
链接：/p/1285
【思路】
图论思想。
很巧妙。
如A+B=C，将AB之间连边，边权为C，用以找相连物品与合成物。
用Dijkstra的思想：找最小价值，如果相连物品中有已经得出最小价值的则共同更新其合成物。
对于方案数用乘法原理在更新的时候顺便计算。
【代码】
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 6 const int maxn = 1000+10; 7 const int INF=1<<30; 8 9 int G[maxn][maxn],d[maxn],vis[maxn];10 int tot[maxn];11 int n;12 13 int main(){14ios::sync_with_stdio(false);15cin>>n;16for(int i=0;i<n;i++) cin>>d[i];1718for(int i=0;i<n;i++) 19{20 tot[i]=1;21 for(int j=0;j<n;j++) G[i][j]=-1;22}2324int u,v,w;25while(cin>>u>>v>>w) {26 G[u][v]=G[v][u]=w;27}28for(int i=0;i<n;i++) {29 int _min=INF,k;30 for(int j=0;j<n;j++) if(!vis[j] && d[j]<_min) _min=d[k=j];31 if(_min==INF) break; 32 vis[k]=1;33 for(int j=0;j<n;j++) if(vis[j] && G[k][j]>=0) //注意是vis[j]//寻找已经得到最小价值的更新其合成物 34 if(d[G[k][j]]>d[k]+d[j]) {35d[G[k][j]]=d[k]+d[j];36tot[G[k][j]]=tot[k]*tot[j];37 }38 else39 if(d[G[k][j]]==d[k]+d[j])40 tot[G[k][j]] += tot[k]*tot[j];41}42cout<<d[0]<<" "<<tot[0]<<"\n";43return 0;44 }
