upc/洛谷p1875--佳佳的魔法药水（最短路+图论模型转化）

upc/洛谷p1875--佳佳的魔法药水（最短路+图论模型转化）

题目大意：

给你n瓶药水，每个药水有一个权值p[i]，你得到新的药水有两种方式 1.直接购买药水C 2.通过两个药水的合成 比如A+B=C 求得到药水0的最小花费和方案数

题解：

这个题求方案数可以想到类似最短路计数，那就需要把它转化成一个图的模型 如果dist[i]代表合成药水i的最低花费，那么如何更新dist[j]的最低花费 传统最短路都是从一个已经确定最短路的点出发，u->v 用u去更新v，这个题是两种药水合成一种药水 那么就从两个已经确定最短路的点出发 ，假如A+B合成C 就用dist[c] >dist[A]+dist[B] 更新 方案数就是最短路计数的模板了

有一个坑点就是 A+A=C的时候，存图的时候只要存一条边就可以了 （18分与100分的区别）

Code

int n,head[maxn],cnt,dist[maxn],vis[maxn],link[1600][1600],ans[maxn];struct node { int u,v,w,next;} e[maxn];void add(int u,int v) { e[cnt].u=u,e[cnt].v=v; e[cnt].next=head[u],head[u]=cnt++;}void slove() { priority_queue,greater > q; rep(i,1,n) q.push({dist[i],i}); while(q.size()) { PII fr= q-(); q.pop(); int dian=fr.second; int dis=fr.first; if(vis[dian]) continue; vis[dian]=1; for(int i= head[dian]; ~i; i=e[i].next) { int v=e[i].v; int w = link[dian][v]; if(vis[v]==0) continue; if(dist[w]>dis+dist[v]) { dist[w]=dis+dist[v]; ans[w] = ans[v]*ans[dian]; q.push({dist[w],w}); } else if(dist[w]==dis+dist[v]) { ans[w]+=ans[v]*ans[dian]; } } }}int main() { n=read(),mst(head,-1); rep(i,1,n) dist[i]=read(),ans[i]=1; int u,v,w; while(cin>>u>>v>>w) { u++,v++,w++; add(u,v); if(u==v) continue; add(v,u); link[v][u]=w,link[u][v]=w; } slove(); printf("%d %d",dist[1],ans[1]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。