반응형
https://www.acmicpc.net/problem/5719
5719번: 거의 최단 경로
문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만
www.acmicpc.net
다잌스트라를 알고있다면 어려운 문제는 아니다. 경로추적과 경로가 여러가지일때 list에 중복적으로 쌓는 스킬이 필요하다. 그리고 경로를 데추적하면서 단방향 그래프를 삭제하면된다. 아직까지 자바가 익숙하지않아서
for을 통해 삭제하고싶은 값을 찾고 있으면 삭제하고 break하는 방법을 사용했다.
나중에 한번 ArrayList를 remove를 인덱스형말고 오브젝트형으로 삭제하면 편할것같은데 그거에대한 연습을 해야겠다. Object형을 삭제할때는 주소값이 필요한데 경로에서 어떻게 받을지도 문제 인것같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class B5719 {
static int N,M;
static int S,D;
static int digit[];
static ArrayList<Integer>[] route;
static class VERTEX implements Comparable<VERTEX>{
int u;
int p;
public VERTEX(int u, int p) {
super();
this.u = u;
this.p = p;
}
@Override
public int compareTo(VERTEX o) {
if(this.p >o.p) {
return 1;
}
return -1;
}
}
static ArrayList<VERTEX>[] ver;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while(true) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if(N==0 && M==0)break;
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
ver = new ArrayList[N];
for(int n=0;n<N;n++) {
ver[n] = new ArrayList<VERTEX>();
}
for(int m=0;m<M;m++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int p = Integer.parseInt(st.nextToken());
ver[u].add(new VERTEX(v, p));
}
route = new ArrayList[N];
//경로수 저장할거임
for(int n=0;n<N;n++) {
route[n] = new ArrayList<Integer>();
}
digit = new int[N];
Arrays.fill(digit, 987654321);
digit[S] = 0;
PriorityQueue<VERTEX> q = new PriorityQueue<VERTEX>();
q.add(new VERTEX(S, 0));
while(!q.isEmpty()) {
VERTEX tmp = q.poll();
int size = ver[tmp.u].size();
for(int s=0;s<size;s++) {
VERTEX next = ver[tmp.u].get(s);
if(digit[next.u] > digit[tmp.u] + next.p) {
digit[next.u] = digit[tmp.u] + next.p;
route[next.u].clear();
route[next.u].add(tmp.u);
q.add(new VERTEX(next.u, digit[tmp.u] + next.p));
}else if(digit[next.u] == digit[tmp.u] + next.p) {
route[next.u].add(tmp.u);
}
}
}
//다잌스트라 최단 경로를 구했다. 이제 경로를 백트래킹하면서 ver을 끊어준다.
backT(D);
//다시 다잌스트라를 구한다.
digit = new int[N];
Arrays.fill(digit, 987654321);
digit[S] = 0;
q = new PriorityQueue<VERTEX>();
q.add(new VERTEX(S, 0));
while(!q.isEmpty()) {
VERTEX tmp = q.poll();
int size = ver[tmp.u].size();
for(int s=0;s<size;s++) {
VERTEX next = ver[tmp.u].get(s);
if(digit[next.u] > digit[tmp.u] + next.p) {
digit[next.u] = digit[tmp.u] + next.p;
q.add(new VERTEX(next.u, digit[tmp.u] + next.p));
}
}
}
if(digit[D]== 987654321) {
System.out.println(-1);
}else {
System.out.println(digit[D]);
}
}
}
public static void backT(int cur) {
int size = route[cur].size();
if(size ==0) {
return;
}
for(int s=0;s<size;s++) {
int next = route[cur].get(s);
for(int i=0;i<ver[next].size();i++) {
if(ver[next].get(i).u == cur){
ver[next].remove(i);
break;
}
}
backT(next);
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
반응형