| 问题描述： | 得到一种药水有两种方法：可以按照魔法书上的指导自己配置，也可以到魔法商店里去买 ——那里对于每种药水都有供应，虽然有可能价格很贵。在魔法书上有很多这样的记载：1 份A药水混合1份B药水就可以得到1份C药水。（至于为什么1+1=1，因为……这是魔法世 界）好了，现在你知道了需要得到某种药水，还知道所有可能涉及到的药水的价格以及魔法 书上所有的配置方法，现在要问的就是：1.最少花多少钱可以配制成功这种珍贵的药水；2. 共有多少种不同的花费最少的方案（两种可行的配置方案如果有任何一个步骤不同则视为不 同的）。假定初始时你手中并没有任何可以用的药水。 | |
| 数据输入： | 第一行有一个整数N，表示一共涉及到的药水总数。药水从0~N-1顺序编号，0号药水就是最 终要配制的药水。 第二行有N个整数，分别表示从0~N-1顺序编号的所有药水在魔法商店的价格（都表示1份的 价格）。 第三行开始，每行有3个整数A、B、C，表示1份A药水混合1份B药水就可以得到1份C药 水。注意，某两种特定的药水搭配如果能配成新药水的话，那么结果是唯一的。也就是说不 会出现某两行的A、B相同但C不同的情况。 输入以一个空行结束。 | |
| 结果输出： | 输出两个用空格隔开的整数，分别表示得到0号药水的最小花费以及花费最少的方案的个 数。 | |
| 样例： | 7 10 5 6 3 2 2 3 1 2 0 4 5 1 3 6 2 | 10 3 |
| 核心思想： | 很汗颜，很惊人，竟然是图论还是最短路。Dijkstra，每次更新能配制的且花费最小的 | |
vard,g:array[0..1010]of longint;a:array[0..1010,0..1010]of longint;b:array[0..1010]of boolean;n:longint;
//==================================================
procedure init;
vari,j,x,y,z:longint;
beginreadln(n);fori:=1 to n do read(d[i]);readln;while not eof dobeginreadln(x,y,z);inc(x);inc(y);inc(z);a[x,y]:=z;a[y,x]:=z;end;
end;
//=============================================
procedure dijkstra;
vari,j,p,min:longint;
beginfillchar(b,sizeof(b),false);fori:=1 to n do g[i]:=1;fori:=1 to n dobeginmin:=maxlongint;for j:=1 to n doif (not b[j])and(d[j]<min) thenbeginmin:=d[j];p:=j;end;ifmin>d[1] then continue;b[p]:=true;for j:=1 to n doif (b[j])and(a[p,j]>0) then{<一个是枚举的最小的，一个是确定的，配出来的将为确定的>}if d[p]+d[j]<d[a[p,j]] thenbegind[a[p,j]]:=d[p]+d[j];g[a[p,j]]:=g[p]*g[j];endelseif d[p]+d[j]=d[a[p,j]] then g[a[p,j]]:=g[a[p,j]]+g[p]*g[j];end;writeln(d[1],' ',g[1]);
end;
//=============================================
beginassign(input,'p1408.in');reset(input);assign(output,'p1408.out');rewrite(output);init;dijkstra;close(output);close(output);
end.本文发布于:2024-02-05 02:36:01，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170722057862241.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
