admin管理员组文章数量:1577824
题意:
用Dijkstra来做,题目在Dijkstra的基础上增加了一些操作,除了要更新dist[] 和 visit[] 数组外,将原算法中记录路径的parent[]数组改为--->记录start至end最短路径上的rescue[],另外还需要一个ways[]数组来更新最短路径的条数。在遇到多条最短路径时,表现为dist[j] == dist[index] + edge[index][j],此时将ways[j] += ways[index]即可。然后比较rescue[j] 与 rescue[index] + weight[j]的大小确定rescue[j]始终是到达j点的所有最短路径中最大的。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int c1 = input.nextInt();
int c2 = input.nextInt();
int i=0, j=0;
int weight[] = new int[n];
for(i=0; i<weight.length; i++)
weight[i] = input.nextInt();
int edge[][] = new int[n][n];
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(i != j) edge[i][j] = Integer.MAX_VALUE;
for(i=0; i<m; i++) {
int a = input.nextInt();
int b = input.nextInt();
edge[a][b] = edge[b][a] = input.nextInt();
}
int dist[] = new int[n];
for(i=0; i<n; i++)
dist[i] = Integer.MAX_VALUE;
boolean visit[] = new boolean[n];
int rescue[] = new int[n];
int ways[] = new int[n];
//dijistra
dist[c1] = 0;
rescue[c1] = weight[c1];
ways[c1] = 1;
int k=0;
for(i=0; i<n; i++) {
int index = -1, min = Integer.MAX_VALUE;
for(k=0; k<n; k++) {
if(!visit[k] && min > dist[k]) {
index = k;
min = dist[k];
}
}
if(index == -1) break;
visit[index] = true;
for(j=0; j<n; j++) {
if(!visit[j] && edge[index][j] != Integer.MAX_VALUE) {
if(dist[index] + edge[index][j] < dist[j]) {
dist[j] = dist[index] + edge[index][j];
rescue[j] = rescue[index] + weight[j];
ways[j] = ways[index];
}
else if(dist[index] + edge[index][j] == dist[j]){
ways[j] += ways[index];
if(rescue[j] < rescue[index] + weight[j])
rescue[j] = rescue[index] + weight[j];
}
}
}
}
System.out.print(ways[c2] + " " + rescue[c2]);
}
}
版权声明:本文标题:1003 Emergency (25 分) java 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1727823473a1131999.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论