[BOJ] 백준 [2307] 도로검문 JAVA

[BOJ] 백준 [2307] 도로검문 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main {

static int N,M;

static ArrayList < int [] > [] list;

static int [] distance,path;

public static void main( String [] args) throws IOException {

BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

int [] input = Arrays.stream(br.readLine(). split ( " " )).mapToInt(Integer:: parseInt ).toArray();

N = input[ 0 ]; M = input[ 1 ];

init();

for ( int i = 0 ;i < M;i + + ){

input = Arrays.stream(br.readLine(). split ( " " ))

.mapToInt(Integer:: parseInt ).toArray();

list[input[ 0 ]]. add ( new int []{input[ 1 ], input[ 2 ]});

list[input[ 1 ]]. add ( new int []{input[ 0 ], input[ 2 ]});

}

path = new int [N + 1 ];

Arrays.fill(path, - 1 );

int shortPath = findShortestPath();

int maxPath = 0 ;

for ( int i = N;i > 0 ;i = path[i])

maxPath = Math.max(maxPath,otherPath(path[i],i));

if (maxPath = = Integer.MAX_VALUE) System . out . println ( - 1 );

else System . out . println (maxPath - shortPath);

}

private static int findShortestPath() {

Arrays.fill(distance,Integer.MAX_VALUE);

distance[ 1 ] = 0 ;

Queue < int [] > q = new PriorityQueue < > ((o1, o2) - > o1[ 1 ] - o2[ 1 ]);

q. add ( new int []{ 1 , 0 });

while ( ! q.isEmpty()){

int [] cur = q.poll();

if (cur[ 1 ] > distance[cur[ 0 ]]) continue ;

for ( int [] next : list[cur[ 0 ]]) {

if (distance[next[ 0 ]] > distance[cur[ 0 ]] + next[ 1 ]){

distance[next[ 0 ]] = distance[cur[ 0 ]] + next[ 1 ];

q. add ( new int []{next[ 0 ],distance[next[ 0 ]]});

path[next[ 0 ]] = cur[ 0 ];

}

}

}

return distance[N];

}

private static int otherPath( int from, int to) {

Arrays.fill(distance,Integer.MAX_VALUE);

distance[ 1 ] = 0 ;

Queue < int [] > q = new PriorityQueue < > ((o1, o2) - > o1[ 1 ] - o2[ 1 ]);

q. add ( new int []{ 1 , 0 });

while ( ! q.isEmpty()){

int [] cur = q.poll();

if (cur[ 1 ] > distance[cur[ 0 ]]) continue ;

for ( int [] next : list[cur[ 0 ]]) {

if (from = = cur[ 0 ] & & to = = next[ 0 ]) continue ;

if (distance[next[ 0 ]] > distance[cur[ 0 ]] + next[ 1 ]){

distance[next[ 0 ]] = distance[cur[ 0 ]] + next[ 1 ];

q. add ( new int []{next[ 0 ],distance[next[ 0 ]]});

}

}

}

return distance[N];

}

private static void init() {

list = new ArrayList[N + 1 ];

for ( int i = 1 ;i < = N;i + + ) list[i] = new ArrayList < > ();

distance = new int [N + 1 ];

}

}

from http://katastrophe.tistory.com/76 by ccl(A) rewrite - 2021-11-05 15:26:24