Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class GG {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int V = in.nextInt();
- int[] vals = new int[V+1];
- int[] dist = new int[V+1];
- int[] itms = new int[V+1];
- boolean[] vis = new boolean[V+1];
- Vector<Pair>[] adjList = new Vector[V+1];
- for(int i = 1; i <= V; i++) {
- vals[i] = in.nextInt();
- adjList[i] = new Vector<Pair>();
- vis[i] = false;
- dist[i] = Integer.MAX_VALUE;
- itms[i] = 0;
- }
- itms[1] = vals[1];
- dist[1] = 0;
- int E = in.nextInt();
- for(int i = 0; i < E ; i++) {
- int u = in.nextInt();
- int v = in.nextInt();
- int w = in.nextInt();
- adjList[u].add(new Pair(v, w));
- adjList[v].add(new Pair(u, w));
- }
- PriorityQueue<Triple> q = new PriorityQueue();
- q.offer(new Triple(1, dist[1], itms[1]));
- while(!q.isEmpty()) {
- Triple state = q.poll();
- int u = state.f;
- int d = state.s;
- int it = state.t;
- for(Pair p : adjList[u]) {
- int v = p.f;
- int w = p.s;
- if(dist[v] > dist[u] + w) {
- dist[v] = Math.min(dist[u] + w, dist[v] );
- itms[v] = vals[v] + itms[u];
- q.offer(new Triple(v, dist[v], itms[v]));
- }else if(dist[v] == (dist[u] + w)) {
- if(itms[v] < itms[u] + vals[v]) {
- itms[v] = itms[u] + vals[v];
- q.offer(new Triple(v, dist[v], itms[v]));
- }
- }
- }
- }
- if(dist[V] == Integer.MAX_VALUE) System.out.println("Impossible");
- else System.out.println(dist[V]+" "+itms[V]);
- }
- }
- class Pair implements Comparable<Pair>{
- int f, s;
- public Pair(int f, int s) {
- this.f = f;
- this.s = s;
- }
- @Override
- public int compareTo(Pair p) {
- return this.s - p.s;
- }
- }
- class Triple implements Comparable<Triple> {
- int f, s, t;
- public Triple(int f, int s, int t) {
- this.f = f;
- this.s = s;
- this.t = t;
- }
- @Override
- public int compareTo(Triple t) {
- return this.s - t.s;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement