NYOJ 203 三国志
nyoj
2023-09-11 14:15:29 时间
三国志
时间限制:3000 ms | 内存限制:65535 KB
难度:5
- 描述
-
《三国志》是一款很经典的经营策略类游戏。我们的小白同学是这款游戏的忠实玩家。现在他把游戏简化一下,地图上只有他一方势力,现在他只有一个城池,而他周边有一些无人占的空城,但是这些空城中有很多不同数量的同种财宝。我们的小白同学虎视眈眈的看着这些城池中的财宝。
按照游戏的规则,他只要指派一名武将攻占这座城池,里面的财宝就归他所有了。不过一量攻占这座城池,我们的武将就要留守,不能撤回。因为我们的小白手下有无数的武将,所以他不在乎这些。
从小白的城池派出的武将,每走一公理的距离就要消耗一石的粮食,而他手上的粮食是有限的。现在小白统计出了地图上城池间的道路,这些道路都是双向的,他想请你帮忙计算出他能得到 的最多的财宝数量。我们用城池的编号代表城池,规定小白所在的城池为0号城池,其他的城池从1号开始计数。
- 输入
- 本题包含多组数据:
首先,是一个整数T(1<=T<=20),代表数据的组数
然后,下面是T组测试数据。对于每组数据包含三行:
第一行:三个数字S,N,M
(1<=S<=1000000,1<=N<=100,1<=M<=10000)
S代表他手中的粮食(石),N代表城池个数,M代表道路条数。
第二行:包含M个三元组行 Ai,Bi,Ci(1<=A,B<=N,1<=C<=100)。
代表Ai,Bi两城池间的道路长度为Ci(公里)。
第三行:包含N个元素,Vi代表第i个城池中的财宝数量。(1<=V<=100) - 输出
- 每组输出各占一行,输出仅一个整数,表示小白能得到的最大财富值。
- 样例输入
-
2 10 1 1 0 1 3 2 5 2 3 0 1 2 0 2 4 1 2 1 2 3
- 样例输出
-
2 5
- 来源
- 郑州大学校赛题目
- 上传者
- 张云聪
-
解题:最短路+0-1背包,先求出0点到各个城市的距离,然后用距离当作代价,在1...n个城市进行背包。1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #include <queue> 10 #define LL long long 11 #define INF 0x3f3f3f3f 12 using namespace std; 13 const int maxn = 110; 14 struct arc{ 15 int to,w; 16 }; 17 vector<arc>g[maxn]; 18 queue<int>q; 19 int s,n,m; 20 int val[maxn],d[maxn],pre[maxn]; 21 int dp[1000010]; 22 bool in[maxn]; 23 void spfa(int src){ 24 int i,j,u,v; 25 for(i = 0; i <= n; i++){ 26 d[i] = INF; 27 in[i] = false; 28 pre[i] = -1; 29 } 30 d[src] = 0; 31 while(!q.empty()) q.pop(); 32 q.push(src); 33 in[src] = true; 34 while(!q.empty()){ 35 u = q.front(); 36 q.pop(); 37 in[u] = false; 38 for(i = 0; i < g[u].size(); i++){ 39 v = g[u][i].to; 40 if(d[v] > d[u]+g[u][i].w){ 41 d[v] = d[u]+g[u][i].w; 42 pre[v] = u; 43 if(!in[v]){ 44 q.push(v); 45 in[v] = true; 46 } 47 } 48 } 49 } 50 } 51 int main(){ 52 int t,i,j,u,v,w; 53 scanf("%d",&t); 54 while(t--){ 55 scanf("%d%d%d",&s,&n,&m); 56 for(i = 0; i <= n; i++) 57 g[i].clear(); 58 for(i = 0; i < m; i++){ 59 scanf("%d%d%d",&u,&v,&w); 60 g[u].push_back((arc){v,w}); 61 g[v].push_back((arc){u,w}); 62 } 63 for(i = 1; i <= n; i++) 64 scanf("%d",val+i); 65 spfa(0); 66 memset(dp,0,sizeof(dp)); 67 for(i = 1; i <= n; i++){ 68 for(j = s; j >= d[i]; j--){ 69 dp[j] = max(dp[j],dp[j-d[i]]+val[i]); 70 } 71 } 72 printf("%d\n",dp[s]); 73 } 74 return 0; 75 }
相关文章
- nyoj 单调递增最长子序列 17 (LIS模板)
- nyoj 一种排序 8 (结构体 排序)
- nyoj 括号匹配(二) 15 (区间dp) 好题
- nyoj 最大和 104 (二维子矩阵 DP) 好题
- NYOJ 1023 还是回文(DP,花最少费用形成回文串)
- nyoj 925 国王的烦恼(最小生成树)
- NYOJ 99单词拼接(有向图的欧拉(回)路)
- NYOJ 483 Nightmare 【广搜】+【无标记】
- nyoj 86 找球号(一)
- nyoj-20-吝啬的国度(深搜)
- NYOJ 70-阶乘因式分解(二)
- NYOJ 1066 CO-PRIME(数论)
- NYOJ 76 超级台阶
- NYOJ 284 坦克大战 【BFS】+【优先队列】
- NYoj-Binary String Matching-KMP算法
- NYOJ 891 找点
- nyoj 105
- NYOJ 116 士兵杀敌 (线段树,区间和)
- nyoj 1239 引水project (河南省第八届acm程序设计大赛)
- NYOJ 821 简单求值【简单题】
- nyoj-655-光棍的yy(大数)
- nyoj 523 亡命逃窜 【BFS】
- NYOJ 623 A*B ProblemII
- nyoj 228 士兵杀死(五岁以下儿童)【树状数组】
- NYOJ 300 && hdu 2276 Kiki & Little Kiki 2 (矩阵高速功率)
- nyoj 题号12 水厂(两)——南阳oj
- NYOJ 1068 ST(段树 为段更新+间隔总和)
- NYOJ 709(ZZULIOJ1481) 异 形 卵
- NYOJ 104 最大子矩阵(二维DP)