admin管理员组文章数量:1577819
文章目录
- PAT 甲级 1003 Emergency (25 分)(Java)
- 题目
- 注意事项
- 解法
- 解法一
PAT 甲级 1003 Emergency (25 分)(Java)
题目
题目链接
注意事项
这题感觉数组量还蛮大的,所以使用了StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));代替Scanner sc = new Scanner(System.in); 效果还是不错的,若是碰到数据量大的,可以使用此法进行输入;
解法
解法一
最短路径,迪杰斯特拉算法;
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
public class Main_1003 {
public static String shortPath(int[][] g, int[] rescue, int start, int end){
int len = g.length;
int[] res = new int[len]; // 最短路径
int[] num = new int[len]; // 最大救援队数量
int[] total = new int[len]; // 最短路径的条数
boolean[] vis = new boolean[len]; //当前节点是否访问过
vis[start] = true;
total[start] = 1;
num[start] = rescue[start];
// 初始化length数组,即start直达其它点的长度;以及vis数组
for(int i=0; i<len; ++i){
if(i == start){
continue;
}
res[i] = g[start][i];
vis[i] = false;
if(res[i] != Integer.MAX_VALUE){
num[i] = num[start] + rescue[i];
total[i] = 1;
}
}
for(int i=0; i<len-1; ++i){ // 从start到其它len-1个位置的最短路径
// 查找当前最短的路径
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int j=0; j<len; ++j){
if(!vis[j] && min > res[j]){
min = res[j];
minIndex = j;
}
}
if(minIndex == -1){
break;
}
// 更新res数组,即经过minIndex点是否缩短了路径
vis[minIndex] = true;
for(int j=0; j<len; ++j){
if(!vis[j] && g[minIndex][j] != Integer.MAX_VALUE && res[j] > res[minIndex] + g[minIndex][j]){
res[j] = res[minIndex] + g[minIndex][j];
num[j] = num[minIndex] + rescue[j];
total[j] = total[minIndex];
}else if(!vis[j] && g[minIndex][j] != Integer.MAX_VALUE && res[j] == res[minIndex] + g[minIndex][j]){
total[j] += total[minIndex];
if(num[j] < num[minIndex] + rescue[j]){
num[j] = num[minIndex] + rescue[j];
}
}
}
}
return "" + total[end] + " " + num[end];
}
public static void main(String[] args) throws IOException {
StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
sc.nextToken();
int n = (int)sc.nval;
sc.nextToken();
int m = (int)sc.nval;
int[][] g = new int[n][n];
for(int i=0; i<n; ++i){
Arrays.fill(g[i], Integer.MAX_VALUE);
}
sc.nextToken();
int start = (int)sc.nval;
sc.nextToken();
int end = (int)sc.nval;
int[] num = new int[n];
for (int i = 0; i < n; i++) {
sc.nextToken();
num[i] = (int)sc.nval;
}
for(int i=0; i<m; ++i){
sc.nextToken();
int x = (int)sc.nval;
sc.nextToken();
int y = (int)sc.nval;
sc.nextToken();
int z = (int)sc.nval;
g[x][y] = z;
g[y][x] = z;
}
System.out.println(shortPath(g, num, start, end));
}
}
版权声明:本文标题:PAT 甲级 1003 Emergency (25 分)(Java) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1727823017a1131948.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论