78 lines
2.3 KiB
Java
78 lines
2.3 KiB
Java
import java.util.*;
|
|
|
|
class Tuple implements Comparable<Tuple> {
|
|
int distance, node;
|
|
|
|
Tuple(int distance, int node) {
|
|
this.distance = distance;
|
|
this.node = node;
|
|
}
|
|
|
|
@Override
|
|
public int compareTo(Tuple other) {
|
|
return Integer.compare(this.distance, other.distance);
|
|
}
|
|
}
|
|
|
|
public class _14938 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
String[] line1 = sc.nextLine().split(" ");
|
|
int n = Integer.parseInt(line1[0]);
|
|
int m = Integer.parseInt(line1[1]);
|
|
int r = Integer.parseInt(line1[2]);
|
|
|
|
String[] line2 = sc.nextLine().split(" ");
|
|
int[] items = new int[n+1];
|
|
for(int i=1; i<=n; i++) items[i] = Integer.parseInt(line2[i-1]);
|
|
|
|
@ SuppressWarnings("unchecked")
|
|
ArrayList<Tuple>[] graph = new ArrayList[n+1];
|
|
for(int i=0; i<=n; i++) graph[i] = new ArrayList<Tuple>();
|
|
|
|
for(int i=0; i<r; i++) {
|
|
String[] line3 = sc.nextLine().split(" ");
|
|
int u = Integer.parseInt(line3[0]);
|
|
int v = Integer.parseInt(line3[1]);
|
|
int w = Integer.parseInt(line3[2]);
|
|
|
|
graph[u].add(new Tuple(w, v));
|
|
graph[v].add(new Tuple(w, u));
|
|
}
|
|
|
|
sc.close();
|
|
|
|
int result = 0;
|
|
for(int start = 1; start<=n; start++) {
|
|
int[] distance = new int[n+1];
|
|
Arrays.fill(distance, 20000000);
|
|
|
|
PriorityQueue<Tuple> pq = new PriorityQueue<>();
|
|
pq.add(new Tuple(0, start)); // (distance, node)
|
|
distance[start] = 0;
|
|
|
|
while (!pq.isEmpty()) {
|
|
Tuple current = pq.poll();
|
|
|
|
if(current.distance > distance[current.node]) continue;
|
|
|
|
for (Tuple next : graph[current.node]) {
|
|
if(distance[next.node] > distance[current.node] + next.distance) {
|
|
distance[next.node] = distance[current.node] + next.distance;
|
|
pq.add(new Tuple(distance[next.node], next.node));
|
|
}
|
|
}
|
|
}
|
|
|
|
int temp = 0;
|
|
for(int i=1; i<=n; i++) {
|
|
if(distance[i] <= m) temp += items[i];
|
|
}
|
|
|
|
result = Math.max(result, temp);
|
|
}
|
|
|
|
System.out.println(result);
|
|
}
|
|
}
|