NYOJ 679 贪婪的商店

贪婪的商店

描述

小明星期天去一家商店买东西，看上了一个玩具，非常想买下来。但是这家商店有这样一个规定，如果要买一件物品A，可能必须要另一件物品B。而要买物品B，可能必须要买另一件物品C。直到买的这件物品不需要买其他物品为止。 经过顾客抗议，商店重新决定如果买一件物品，所需要买其他物品超过一件的话，可以买其中任一件就好。小明钱不多了，他想知道如果要买这件物品，最少要花多少钱。

输入

第一行包含一个整数T（T <= 100).表示测试数据组数。
每组数据第一行包含三个整数N,M,P（1 <= P <= N <= 1000,0 <= m <= 10000),
分别表示商店物品总个数，物品之间关系数量，小明想买物品的编号。

接下来的一行包含N个整数Vi，表示第i个物品的价钱。
接下来的M行每行包含两个整数a,b（1 <= a,b <= N)，表示要买物品a就可能要买物品b。

输出

输出“Case #i: ans”（不含引号），i表示第i组数据，ans表示最少花的钱数。

样例输入

2
4 4 1
1 3 2 4
1 2
2 3
2 4
3 4
4 4 2
2 1 3 4
1 2
2 4
1 3
3 4

样例输出

Case #1: 8
Case #2: 5

简单树型DP！

AC码：

#include
       
        
#include
        
          #include
         
           #include
          
            using namespace std; #define MAX 1005 #define INF 9999999 vector
           
             adj[MAX]; int dp[MAX],visit[MAX]; int weight[MAX]; int Min(int a,int b) { return a>b b:a; } void DFS(int u) { if(visit[u]) return; int len=adj[u].size(),v; if(len==0) { dp[u]=weight[u]; return; } for(int i=0;i
            
             

             

            
           
          
         
        
       
						

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： C++ Primer 学习笔记_72_面向对象编程 --句柄类与继承[续]

下一篇： C++ Primer 学习笔记_71_面向对象编程 --句柄类与继承

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");