生活随笔
收集整理的這篇文章主要介紹了
nyoj203（迪杰斯特拉+01背包）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
三國志
時間限制：
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
解題思路：這道題目比較容易懂，弄清楚題意后就應該有思路。。注意題目有重邊，要取最小的。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int inf = 65535;
int s,n,m,map[110][110];
int dis[110],dp[1000010],num[110];void dijkstra()
{int k,minn = inf;bool vis[110];memset(vis,false,sizeof(vis));
/* for(int i = 1; i <= n; i++){dis[i] = map[0][i];if(dis[i] < minn){minn = dis[i];k = i;}}vis[k] = true;for(int j = 1; j <= n; j++){if(vis[j] == true) continue;if(dis[j] > minn + map[k][j])dis[j] = minn + map[k][j];}*/for(int i = 1; i <= n; i++) dis[i] = map[0][i];for(int i = 1; i <= n; i++){minn = inf;for(int j = 1; j <= n; j++){if(vis[j] == true) continue;if(minn > dis[j]){minn = dis[j];k = j;}}vis[k] = true;for(int j = 1; j <= n; j++){if(vis[j] == true) continue;if(dis[j] > minn + map[k][j])dis[j] = minn + map[k][j];}}
}int main()
{ int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&s,&n,&m);for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)map[i][j] = inf;for(int i = 1; i <= m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);map[a][b] = min(map[a][b],c);map[b][a] = map[a][b];}for(int i = 1; i <= n; i++)scanf("%d",&num[i]);dijkstra(); //尋求最短路//典型的01背包問題memset(dp,0,sizeof(dp));for(int i = 1; i <= n; i++)for(int j = s; j >= dis[i]; j--){dp[j] = max(dp[j],dp[j-dis[i]]+num[i]);}printf("%d\n",dp[s]);}return 0;
}
與50位技術專家面對面20年技術見證，附贈技術全景圖
總結
以上是生活随笔為你收集整理的nyoj203（迪杰斯特拉+01背包）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
