當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

NYOJ 203 三国志(Dijkstra+贪心)

發布時間：2025/3/16 编程问答 19 豆豆

生活随笔收集整理的這篇文章主要介紹了 NYOJ 203 三国志(Dijkstra+贪心) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

三國志

時間限制：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

Dijkstra+貪心算法！

AC碼：

#include<stdio.h> #include<string.h> #define INF 99999999 int G[105][105],visit[105],num[105]; int dist[105],dp[1000005]; int max(int a,int b) {return a>b?a:b; } int main() {int T,s,n,m,a,b,c,min,i,j,k;scanf("%d",&T);while(T--){scanf("%d%d%d",&s,&n,&m);for(i=0;i<=n;i++){for(j=0;j<=n;j++)G[i][j]=INF;}for(i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);if(G[a][b]>c) // WA了很多次，不知道為什么要加這個判斷條件G[a][b]=G[b][a]=c; // 創建鄰接矩陣}for(i=1;i<=n;i++)scanf("%d",&num[i]); // 每個城市的財富值// Dijkstra算法求任意兩點間的最短路徑memset(visit,0,sizeof(visit));for(i=0;i<=n;i++)dist[i]=G[0][i];dist[0]=0;visit[0]=1;for(i=1;i<=n;i++){min=INF;k=0;for(j=0;j<=n;j++){if(!visit[j]&&min>dist[j]){min=dist[j];k=j;}}visit[k]=1;for(j=0;j<=n;j++){if(!visit[j]&&dist[j]>dist[k]+G[k][j])dist[j]=dist[k]+G[k][j];}}// 最短路徑求解完畢// 貪心算法求得最大財富值memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){for(j=s;j>=dist[i];j--){dp[j]=max(dp[j],dp[j-dist[i]]+num[i]);}}printf("%d\n",dp[s]);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 203 三国志(Dijkstra+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： NYOJ 70 阶乘因式分解(二)
下一篇： NYOJ 325 zb的生日