三國(guó)志

時(shí)間限制：3000 ms ?|? 內(nèi)存限制：65535 KB 難度：5 描述

《三國(guó)志》是一款很經(jīng)典的經(jīng)營(yíng)策略類(lèi)游戲。我們的小白同學(xué)是這款游戲的忠實(shí)玩家。現(xiàn)在他把游戲簡(jiǎn)化一下，地圖上只有他一方勢(shì)力，現(xiàn)在他只有一個(gè)城池，而他周邊有一些無(wú)人占的空城，但是這些空城中有很多不同數(shù)量的同種財(cái)寶。我們的小白同學(xué)虎視眈眈的看著這些城池中的財(cái)寶。

按照游戲的規(guī)則，他只要指派一名武將攻占這座城池，里面的財(cái)寶就歸他所有了。不過(guò)一量攻占這座城池，我們的武將就要留守，不能撤回。因?yàn)槲覀兊男“资窒掠袩o(wú)數(shù)的武將，所以他不在乎這些。

從小白的城池派出的武將，每走一公理的距離就要消耗一石的糧食，而他手上的糧食是有限的。現(xiàn)在小白統(tǒng)計(jì)出了地圖上城池間的道路，這些道路都是雙向的，他想請(qǐng)你幫忙計(jì)算出他能得到 的最多的財(cái)寶數(shù)量。我們用城池的編號(hào)代表城池，規(guī)定小白所在的城池為0號(hào)城池，其他的城池從1號(hào)開(kāi)始計(jì)數(shù)。

輸入

本題包含多組數(shù)據(jù)：
首先，是一個(gè)整數(shù)T(1<=T<=20)，代表數(shù)據(jù)的組數(shù)
然后，下面是T組測(cè)試數(shù)據(jù)。對(duì)于每組數(shù)據(jù)包含三行：
第一行：三個(gè)數(shù)字S,N,M
（1<=S<=1000000,1<=N<=100,1<=M<=10000)
S代表他手中的糧食（石），N代表城池個(gè)數(shù)，M代表道路條數(shù)。
第二行：包含M個(gè)三元組行 Ai,Bi,Ci(1<=A,B<=N,1<=C<=100)。
代表Ai,Bi兩城池間的道路長(zhǎng)度為Ci(公里）。
第三行：包含N個(gè)元素，Vi代表第i個(gè)城池中的財(cái)寶數(shù)量。(1<=V<=100)

輸出

每組輸出各占一行，輸出僅一個(gè)整數(shù)，表示小白能得到的最大財(cái)富值。

樣例輸入

2 10 1 1 0 1 3 2 5 2 3 0 1 2 0 2 4 1 2 1 2 3

樣例輸出

2 5

來(lái)源

鄭州大學(xué)校賽題目

上傳者

張?jiān)坡?/p>

#include<stdio.h> #include<string.h> #include<algorithm> #define INF 0x3f3f3f3f #define N 110 using namespace std; int map[N][N]; int vis[N]; int dis[N]; int d[N]; int dp[N*10000]; int z,n,m; int dijst() {int min,i,j,k,sum;memset(vis,0,sizeof(vis));for(i=0;i<=n;i++)dis[i]=map[0][i];vis[0]=1;for(j=1;j<=n;j++){min=INF;k=0;for(i=0;i<=n;i++){if(!vis[i]&&dis[i]<min){k=i;min=dis[i];}}vis[k]=1;for(i=0;i<=n;i++){if(!vis[i]&&dis[k]+map[k][i]<dis[i])dis[i]=dis[k]+map[k][i];}} } int main() {int t,a,b,c,i,j;scanf("%d",&t);while(t--){memset(map,INF,sizeof(map)); scanf("%d%d%d",&z,&n,&m);while(m--){scanf("%d%d%d",&a,&b,&c);if(c<map[a][b])map[a][b]=map[b][a]=c;}for(i=1;i<=n;i++)scanf("%d",&d[i]); dijst();memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){for(j=z;j>=dis[i];j--){dp[j]=max(dp[j],dp[j-dis[i]]+d[i]);}}printf("%d\n",dp[z]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/playboy307/p/5273723.html

總結(jié)

以上是生活随笔為你收集整理的nyoj--203--三国志（迪杰斯特拉+背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。