https://www.acmicpc.net/problem/11657
11657번: 타임머신
첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.
www.acmicpc.net
분류 : 벨만 포드 알고리즘
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char nextChar() {
return next().charAt(0);
}
}
public class Main {
public static PrintWriter out;
public static final int inf = Integer.MAX_VALUE/2;
public static void main(String[] args) throws IOException {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int N = sc.nextInt();
int M = sc.nextInt();
int[] dist = new int[N];
Vector<Edge>[] edge = (Vector<Edge>[]) new Vector[N];
for(int i=0;i<N;i++)
{
edge[i] = new Vector<Edge>();
}
for(int i=0;i<M;i++)
{
int t1 = sc.nextInt();
int t2 = sc.nextInt();
int t3 = sc.nextInt();
edge[t1-1].add(new Edge(t2-1,t3));
}
Arrays.fill(dist, inf);
dist[0]=0;
boolean cycle = false;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
for(Edge e: edge[j]){
int v = e.v;
int cost = e.cost;
if(dist[j]!=inf && dist[v]>dist[j]+cost){
dist[v] = dist[j] +cost;
if(i==N-1) cycle = true;
}
}
}
}
if(cycle) out.println(-1);
else{
for(int i=1;i<N;i++){
out.println(dist[i]!=inf ? dist[i]: -1);
}
}
out.flush();
}
}
class Edge {
int v,cost;
public Edge(int v, int cost){
this.v=v;
this.cost=cost;
}
}
음수 간선치가 있기 때문에 벨만 - 포드 알고리즘으로 풀 수 있는 문제.
다른 코드들도 참조 하여 벨만 - 포드에 대해 공부하고 이해하려고 했지만
내게는 "라이" 라는 분의 블로그의 설명이 제일 잘 와닿아서 참조하여 문제 해결 완료..
'PS' 카테고리의 다른 글
[BOJ]7569번 : 토마토 (0) | 2017.03.29 |
---|---|
[BOJ]10974번 : 모든 순열 (0) | 2017.03.29 |
[BOJ]4195번 : 친구 네트워크 (0) | 2017.03.25 |
[BOJ]1976번 : 여행 가자 (0) | 2017.03.25 |
[BOJ]1717번 : 집합의 표현 (0) | 2017.03.25 |