Aizu Online Judge 0117 A Reward a Carpenter

■0117 A Reward a Carpenter

(殿様から大工が受け取ったお金)-(柱の代金)-(出発町から山里までの総交通費)-(山里から出発町までの総交通費)が答え．後ろ2つは，それぞれDijkstraで求めれば良い．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.   
18.  void run(){  
19.   sc.useDelimiter("[,]|(\\s)+");  
20.   n=sc.nextInt();  
21.   m=sc.nextInt();  
22.   @SuppressWarnings("unchecked")  
23.   LinkedList<E>[] es=new LinkedList[n];  
24.   for(int i=0; i<n; i++){  
25.    es[i]=new LinkedList<E>();  
26.   }  
27.   
28.   for(int i=0; i<m; i++){  
29.    int u=sc.nextInt()-1;  
30.    int v=sc.nextInt()-1;  
31.    int cost1=sc.nextInt();  
32.    int cost2=sc.nextInt();  
33.    es[u].add(new E(v, cost1));  
34.    es[v].add(new E(u, cost2));  
35.   }  
36.   
37.   int s=sc.nextInt()-1;  
38.   int g=sc.nextInt()-1;  
39.   int m1=sc.nextInt();  
40.   int m2=sc.nextInt();  
41.   
42.   int ans=m1-m2-(dijkstra(es, s, g)+dijkstra(es, g, s));  
43.   println(""+ans);  
44.  }  
45.   
46.  int dijkstra(LinkedList<E>[] es, int s, int g){  
47.   int n=es.length;  
48.   int[] d=new int[n];  
49.   PriorityQueue<P> que=new PriorityQueue<P>();  
50.   
51.   Arrays.fill(d, INF);  
52.   d[s]=0;  
53.   que.offer(new P(s, 0));  
54.   for(; !que.isEmpty();){  
55.    P p=que.poll();  
56.    if(d[p.v]<p.d){  
57.     continue;  
58.    }  
59.    for(E e : es[p.v]){  
60.     if(d[e.to]>d[p.v]+e.cost){  
61.      d[e.to]=d[p.v]+e.cost;  
62.      que.offer(new P(e.to, d[e.to]));  
63.     }  
64.    }  
65.   }  
66.   return d[g];  
67.  }  
68.   
69.  class E{  
70.   int to, cost;  
71.   
72.   E(int to, int cost){  
73.    this.to=to;  
74.    this.cost=cost;  
75.   }  
76.  }  
77.   
78.  class P implements Comparable<P>{  
79.   int v, d;  
80.   
81.   P(int v, int d){  
82.    this.v=v;  
83.    this.d=d;  
84.   }  
85.   
86.   @Override  
87.   public int compareTo(P p){  
88.    return d-p.d;  
89.   }  
90.   
91.   @Override  
92.   public String toString(){  
93.    return v+","+d;  
94.   }  
95.  }  
96.   
97.  void debug(Object... os){  
98.   System.err.println(Arrays.deepToString(os));  
99.  }  
100.   
101.  void print(String s){  
102.   System.out.print(s);  
103.  }  
104.   
105.  void println(String s){  
106.   System.out.println(s);  
107.  }  
108.   
109.  public static void main(String[] args){  
110.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
111.   new Main().run();  
112.  }  
113. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;

 void run(){
  sc.useDelimiter("[,]|(\\s)+");
  n=sc.nextInt();
  m=sc.nextInt();
  @SuppressWarnings("unchecked")
  LinkedList<E>[] es=new LinkedList[n];
  for(int i=0; i<n; i++){
   es[i]=new LinkedList<E>();
  }

  for(int i=0; i<m; i++){
   int u=sc.nextInt()-1;
   int v=sc.nextInt()-1;
   int cost1=sc.nextInt();
   int cost2=sc.nextInt();
   es[u].add(new E(v, cost1));
   es[v].add(new E(u, cost2));
  }

  int s=sc.nextInt()-1;
  int g=sc.nextInt()-1;
  int m1=sc.nextInt();
  int m2=sc.nextInt();

  int ans=m1-m2-(dijkstra(es, s, g)+dijkstra(es, g, s));
  println(""+ans);
 }

 int dijkstra(LinkedList<E>[] es, int s, int g){
  int n=es.length;
  int[] d=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  d[s]=0;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }
  return d[g];
 }

 class E{
  int to, cost;

  E(int to, int cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v, d;

  P(int v, int d){
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }

  @Override
  public String toString(){
   return v+","+d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}