nyist203 三国志 (最短路径-01背包)
【摘要】
三国志 (nyist 203)
解题思路请看代码块中的注释~
JAVA版AC代码:
package nyist.part8graph;
import java.util.Arrays;
i...
三国志 (nyist 203)
解题思路请看代码块中的注释~
JAVA版AC代码:
package nyist.part8graph;
import java.util.Arrays;
import java.util.Scanner;
/**
* 考查算法:最短路,01背包
* 由于每个武将到达一个城池后,如果拿下宝藏,就得留下来镇守,即不能离开,
* 所以可以使用Dijkstra算法求得从0(源点)到达每一城池的最短路径,即为最小费用dis[i],
* 而每个城池的宝藏数量则为价值w[i]。
* 题目已知总费用为输入的s,求最大花费不超过s的情况下,能取得的最大价值为多少dp[s]。
* 那么本题将转化成一个01背包问题。
* 状态转移方程为dp[v] = max(dp[v], dp[v-dis[i]]+w[i])
* Created by jal on 2018/5/24 0024.
*/
public class NYIST203最短路径01背包 {
private static int n,m;
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
while (T-->0){
int s = cin.nextInt();
n = cin.nextInt();
m = cin.nextInt();
int [][]a = new int[n+2][n+2];
for (int i = 0; i <= n; i++){
for (int j = 0; j <= n; j++){
if (i == j){
a[i][j] = 0;
}else {
a[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 1; i <= m; i++){
int u = cin.nextInt();
int v = cin.nextInt();
int w = cin.nextInt();
w = Math.min(a[u][v], w); //此处很关键,一定要写,因为两点之间会有多条边,邻接矩阵记录最小边
a[u][v] = w;
a[v][u] = w;
}
int []w = new int[n+1];
for (int i = 1; i<=n; i++){
w[i] = cin.nextInt();
}
Dijkstra(a, 0);
int []dp = new int[s+1];
for(int i = 1; i <= n; i++){
for(int v = s; v >= dis[i]; v--){
dp[v] = Math.max(dp[v], dp[v-dis[i]]+w[i]);
}
}
System.out.print(String.format("%d\n",dp[s]));
}
}
static int []dis;
private static void Dijkstra(int [][]a, int start) {
boolean []book = new boolean[n+1];
dis = new int[n+1];
Arrays.fill(book,false);
for (int i = 0; i <= n; i++){
dis[i] = a[start][i];
}
book[start] = true;
dis[start] = 0;
for (int i = 1; i <= n; i++){
int min = Integer.MAX_VALUE;
int k = 0;
for (int j = 0; j <= n; j++){
if (book[j] == false && dis[j] < min){
min = dis[j];
k = j;
}
}
book[k] = true;
for (int j = 0; j <= n; j++){
if (book[j] == false && a[k][j] < Integer.MAX_VALUE){
dis[j] = Math.min(dis[j], dis[k] + a[k][j]);
}
}
}
}
}
/*
2
10 1 1
0 1 3
2
5 2 3
0 1 2
0 2 4
1 2 1
2 3
* */
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
文章来源: blog.csdn.net,作者:爱玲姐姐,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/jal517486222/article/details/80441539
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)