daily pastebin goal
50%
SHARE
TWEET

FREETICKET Solutio

a guest Jan 5th, 2015 160 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.Scanner;
  8. import java.math.*;
  9.  
  10. public class FREETICKET{
  11.        
  12.         public static final int INF = Integer.MAX_VALUE;
  13.  
  14.         public static void main(String args[]) throws IOException {
  15.                 Scanner in = new Scanner(System.in);
  16.                
  17.                 int c = in.nextInt();
  18.                 int f = in.nextInt();
  19.                
  20.                 int[][] flights = new int[c][c];
  21.                
  22.                 for (int i = 0; i < c; i++) {
  23.                         for (int j = 0; j < c; j++) {
  24.                                 flights[i][j] = -1;
  25.                         }
  26.                 }
  27.                
  28.                 for (int i = 0 ; i < f; i++) {
  29.                         int a = in.nextInt() - 1;
  30.                         int b = in.nextInt() - 1;
  31.                         int w = in.nextInt();
  32.                         flights[a][b] = w;
  33.                         flights[b][a] = w;
  34.                 }
  35.                
  36.                 int max_cost = -10;
  37.                
  38.                 for (int i =0; i < c; i++) {
  39.                         int[] dist = new int[c];
  40.                         boolean[] visited = new boolean[c];
  41.                        
  42.                         for (int j = 0; j < c; j++) {
  43.                                 dist[j] = flights[i][j];
  44.                                 visited[j] = false;
  45.                         }
  46.                        
  47.                         visited[i] = true;
  48.                        
  49.                         while (true) {
  50.                                 int min_flight = -1;
  51.                                 int min_dist = INF;
  52.                                
  53.                                 for (int j = 0; j < c ; j++) {
  54.                                         if (dist[j] != -1 && !visited[j] && dist[j] < min_dist) {
  55.                                                 min_dist = dist[j];
  56.                                                 min_flight = j;
  57.                                         }
  58.                                 }
  59.                                
  60.                                 if (min_flight == -1) {
  61.                                         break;
  62.                                 }
  63.                                
  64.                                 visited[min_flight] =  true;
  65.                                
  66.                                 if (min_dist> max_cost) {
  67.                                         max_cost = min_dist;
  68.                                 }
  69.                                
  70.                                 for (int j = 0; j < c; j++) {
  71.                                         if (flights[min_flight][j] != -1) {
  72.                                                 if (dist[j] == -1 || dist[j] > min_dist + flights[min_flight][j]) {
  73.                                                         dist[j] = min_dist + flights[min_dist][j];
  74.                                                 }
  75.                                         }
  76.                                 }
  77.                        
  78.                                
  79.                         }
  80.                        
  81.                        
  82.                        
  83.                 }
  84.                
  85.                 System.out.println(max_cost);  
  86.         }
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top