feVZPptn

1import java.util.*;
2
3
4class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>>{  // E data
5    private E data;
6    private double minDistance;
7    private Vertex predecessor;
8
9    public Vertex(E data,double minDistance,Vertex predecessor){
10        this.data = data;
11        this.minDistance = minDistance;
12        this.predecessor = predecessor;
13    }
14
15    public Vertex(E data,double minDistance){
16        this.data = data;
17        this.minDistance = minDistance;
18        this.predecessor = null;
19    }
20
21    public Vertex(E data){
22        this.data = data;
23        this.minDistance = Double.MAX_VALUE;
24        this.predecessor = null;
25    }
26
27    public boolean hasPredecessor(){
28        return this.predecessor != null;
29    }
30
31    public double getMinDistance() {
32        return minDistance;
33    }
34
35    public void setMinDistance(double minDistance) {
36        this.minDistance = minDistance;
37    }
38
39    public Vertex<E> getPredecessor() {
40        return predecessor;
41    }
42
43    public void setPredecessor(Vertex predecessor) {
44        this.predecessor = predecessor;
45    }
46
47    public E getData() {
48        return data;
49    }
50
51    public void setData(E data) {
52        this.data = data;
53    }
54
55    @Override
56    public int compareTo(Vertex<E> v) {
57        return Double.compare(minDistance, v.getMinDistance());
58    }
59
60    @Override
61    public int hashCode() {
62        int hash = 3;
63        hash = 29 * hash + Objects.hashCode(this.data);
64        return hash;
65    }
66
67    @Override
68    public boolean equals(Object obj) {
69        if (this == obj) {
70            return true;
71        }
72        if (obj == null) {
73            return false;
74        }
75        if (getClass() != obj.getClass()) {
76            return false;
77        }
78        final Vertex<E> other = (Vertex<E>) obj;
79        if (!this.data.equals(other.data)) {
80            return false;
81        }
82        return true;
83    }
84
85    @Override
86    public String toString(){
87        StringBuilder sb = new StringBuilder();
88        sb.append("Vertex with data: " + this.data + " minDist: " + this.minDistance + " Pred: " + this.predecessor);
89        return sb.toString();
90    }
91
92}
93
94class Edge<E extends Comparable<E>>{
95    private Vertex<E> source;
96    private Vertex<E> destination;
97    private double weight;
98
99    public Edge(Vertex<E> source, Vertex<E> destination, double weight) {
100        this.source = source;
101        this.destination = destination;
102        this.weight = weight;
103    }
104
105    public Vertex<E> getSource() {
106        return source;
107    }
108
109    public void setSource(Vertex<E> source) {
110        this.source = source;
111    }
112
113    public Vertex<E> getDestination() {
114        return destination;
115    }
116
117    public void setDestination(Vertex<E> destination) {
118        this.destination = destination;
119    }
120
121    public double getWeight() {
122        return weight;
123    }
124
125    public void setWeight(double weight) {
126        this.weight = weight;
127    }
128
129    @Override
130    public String toString(){
131        StringBuilder sb = new StringBuilder();
132        sb.append("Edge from: ").append(this.source.toString())
133                .append("\nTo: ").append(this.destination.toString())
134                .append("\nWith weight: " + this.weight);
135        return sb.toString();
136    }
137
138
139
140}
141class Graph<E extends Comparable<E>>{
142
143    List<Vertex<E>> vertices;
144    List<Edge<E>> edges;
145    Map<E,Integer> indexes; // Integer : na koe mesto vo listata e
146
147    public Graph(){
148        vertices = new ArrayList<>();
149        edges = new ArrayList<>();
150        indexes = new HashMap<>();
151    }
152
153    public void addVertex(E data){
154        Vertex<E> vertex = new Vertex<>(data);
155        vertices.add(vertex);
156        int index = vertices.size() - 1;
157        indexes.put(data, index);
158    }
159
160    public Vertex<E> getVertex(E data){
161        return vertices.get(indexes.get(data));
162    }
163
164    private boolean addEdge(Vertex<E> source,Vertex<E> destination,double weight){
165        return edges.add(new Edge<E>(source,destination,weight));
166    }
167
168    public boolean addEdge(E source,E destination,double weight){
169        Vertex<E> s = vertices.get(indexes.get(source));
170        Vertex<E> d = vertices.get(indexes.get(destination));
171        return addEdge(s,d,weight);
172    }
173    public boolean addEdgeBeetween(E source,E destination,double weight){
174        Vertex<E> s = vertices.get(indexes.get(source));
175        Vertex<E> d = vertices.get(indexes.get(destination));
176
177        return addEdge(s,d,weight) && addEdge(d,s,weight);
178    }
179
180    public List<Vertex<E>> getVertices(){
181        return this.vertices;
182    }
183
184    public List<Edge<E>> getEdges(){
185        return this.edges;
186    }
187
188    @Override
189    public String toString(){
190        StringBuilder sb = new StringBuilder();
191        for (Vertex<E> v : this.getVertices()){
192            sb.append(v.toString() + "\n");
193        }
194        return sb.toString();
195    }
196
197    public double getMinDistanceBetweenDijkstra(E start,E end){
198        Vertex<E> source = vertices.get(indexes.get(start));
199        Vertex<E> destination = vertices.get(indexes.get(end));
200        Dijkstra<E> dijkstra = new Dijkstra<>();
201
202        dijkstra.run(this, source);
203
204        return destination.getMinDistance();
205    }
206
207    public double getMinDistanceBetweenBellmanFord(E start,E end){
208        Vertex<E> source = vertices.get(indexes.get(start));
209        Vertex<E> destination = vertices.get(indexes.get(end));
210
211        BellmanFord<E> bellmanFord = new BellmanFord<>();
212
213        if (bellmanFord.run(this, source))
214            return destination.getMinDistance();
215
216        else
217            return -1;
218    }
219}
220
221class Dijkstra<E extends Comparable<E>>{
222
223    public Dijkstra(){
224    }
225
226    private Hashtable<Vertex<E>, List<Edge<E> > > makeHashtable(Graph<E> graph){
227        Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
228        List<Edge<E>> lst;
229        for (Vertex<E> v : graph.getVertices()){
230            lst = new LinkedList<>();
231            table.put(v,lst);
232        }
233
234        for (Edge<E> e : graph.getEdges()){
235            table.get(e.getSource()).add(e);
236        }
237
238        return table;
239    }
240    public void run(Graph<E> graph, Vertex<E> startVertex){
241
242        if (graph == null || startVertex == null)
243            return;
244
245        for (Vertex<E> v : graph.getVertices()){
246            v.setMinDistance(Double.MAX_VALUE);
247            v.setPredecessor(null);
248        }
249
250        startVertex.setMinDistance(0d);
251        PriorityQueue<Vertex<E>> queue = new PriorityQueue<>(graph.getVertices());
252        Hashtable<Vertex<E>, List<Edge<E>>> table = makeHashtable(graph);
253
254        while (!queue.isEmpty()){
255            Vertex<E> u = queue.poll();
256
257            for (Edge<E> e : table.get(u)){
258                Vertex<E> v = e.getDestination();
259                if (v.getMinDistance() > u.getMinDistance() + e.getWeight()){
260                    v.setMinDistance(u.getMinDistance() + e.getWeight());
261                    v.setPredecessor(u);
262                    queue.add(v);
263                }
264            }
265        }
266
267    }
268
269}
270
271class BellmanFord<E extends Comparable<E>>{
272
273    private void relax(Edge<E> edge){
274        if (edge.getDestination().getMinDistance() > edge.getSource().getMinDistance() + edge.getWeight()){
275            edge.getDestination().setMinDistance(edge.getSource().getMinDistance() + edge.getWeight());
276            edge.getDestination().setPredecessor(edge.getSource());
277        }
278    }
279    public boolean run(Graph<E> graph, Vertex<E> startVertex){
280        if (graph == null || startVertex == null)
281            return false;
282
283        for (Vertex<E> v : graph.getVertices()){
284            v.setMinDistance(Double.MAX_VALUE);
285            v.setPredecessor(null);
286        }
287
288        startVertex.setMinDistance(0d);
289
290        for (int i = 0; i < graph.getVertices().size(); i++){
291            for (Edge<E> edge : graph.getEdges()){
292                relax(edge);
293            }
294        }
295
296        for (Edge<E> edge : graph.getEdges()){
297            if (edge.getDestination().getMinDistance() > edge.getSource().getMinDistance() + edge.getWeight()){
298                return false;
299            }
300        }
301
302        return true;
303    }
304}
305
306
307class Bipartite {
308
309    // This function returns true if graph
310    // G[V][V] is Bipartite, else false
311    public static boolean isBipartiteUtil(int G[][], int src,
312                                          int colorArr[])
313    {
314        int V = G.length;
315        colorArr[src] = 1;
316
317        // Create a queue (FIFO) of vertex numbers and
318        // enqueue source vertex for BFS traversal
319        LinkedList<Integer> q = new LinkedList<Integer>();
320        q.add(src);
321
322        // Run while there are vertices in queue
323        // (Similar to BFS)
324        while (!q.isEmpty())
325        {
326            // Dequeue a vertex from queue
327            // ( Refer http://goo.gl/35oz8 )
328            int u = q.getFirst();
329            q.pop();
330
331            // Return false if there is a self-loop
332            if (G[u][u] == 1)
333                return false;
334
335            // Find all non-colored adjacent vertices
336            for (int v = 0; v < V; ++v)
337            {
338                // An edge from u to v exists and
339                // destination v is not colored
340                if (G[u][v] ==1 && colorArr[v] == -1)
341                {
342                    // Assign alternate color to this
343                    // adjacent v of u
344                    colorArr[v] = 1 - colorArr[u];
345                    q.push(v);
346                }
347
348                // An edge from u to v exists and
349                // destination v is colored with same
350                // color as u
351                else if (G[u][v] ==1 && colorArr[v] ==
352                        colorArr[u])
353                    return false;
354            }
355        }
356
357        // If we reach here, then all adjacent vertices
358        // can be colored with alternate color
359        return true;
360    }
361
362    // Returns true if G[][] is Bipartite, else false
363    public static boolean isBipartite(int G[][])
364    {
365        // Create a color array to store colors assigned
366        // to all veritces. Vertex/ number is used as
367        // index in this array. The value '-1' of
368        // colorArr[i] is used to indicate that no color
369        // is assigned to vertex 'i'. The value 1 is used
370        // to indicate first color is assigned and value
371        // 0 indicates second color is assigned.
372        int V = G.length;
373        int colorArr[] = new int[V];
374        for (int i = 0; i < V; ++i)
375            colorArr[i] = -1;
376
377        // This code is to handle disconnected graoh
378        for (int i = 0; i < V; i++)
379            if (colorArr[i] == -1)
380                if (isBipartiteUtil(G, i, colorArr) == false)
381                    return false;
382
383        return true;
384    }
385
386    /* Driver program to test above function */
387}
388
389class Main {
390    public static void main(String[] args) {
391        Scanner s = new Scanner(System.in);
392        int n = s.nextInt();
393        int m = s.nextInt();
394
395        int start = s.nextInt();
396        int end = s.nextInt();
397
398        Graph<Integer> graph = new Graph<>();
399
400        for(int i=1;i<=n;i++){
401            graph.addVertex(i);
402        }
403
404        for(int i=0;i<m;i++) {
405            graph.addEdgeBeetween(s.nextInt(), s.nextInt(), s.nextInt());
406        }
407
408        System.out.println(graph.getMinDistanceBetweenBellmanFord(start,end));
409
410
411    }
412}