forked from hughbzhang/Competitive_Programming
-
Notifications
You must be signed in to change notification settings - Fork 0
/
butter.java
128 lines (112 loc) · 3.6 KB
/
butter.java
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
package Solved;
/*
ID: bigfish2
LANG: JAVA
TASK: butter
*/
import java.awt.Point;
import java.io.*;
import java.util.*;
public class butter {
public static void main (String [] args) throws IOException {
BufferedReader f = new BufferedReader(new FileReader("butter.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("butter.out")));
StringTokenizer st = new StringTokenizer(f.readLine());
//System.out.println("start");
int cows = Integer.parseInt(st.nextToken());
int pastures = Integer.parseInt(st.nextToken());
int paths = Integer.parseInt(st.nextToken());
int[] loc = new int[cows];
int[][] adj = new int[pastures][pastures];
int[][] edge = new int[pastures][pastures];
boolean [] past = new boolean[pastures];
for(int y = 0;y<pastures;y++){
for(int x = 0;x<pastures;x++){
adj[y][x] = Integer.MAX_VALUE;
edge[y][x] = -1;
}
}
for(int x = 0;x<cows;x++){
loc[x] = Integer.parseInt(f.readLine())-1;
}
for(int x = 0;x<paths;x++){
st = new StringTokenizer(f.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
adj[a][b] = Integer.parseInt(st.nextToken());
adj[b][a] = adj[a][b];
}
for(int x = 0;x<pastures;x++) adj[x][x] = 0;
int counter = 0;
for(int x = 0;x<pastures;x++){
for(int a = 0;a<pastures;a++){
if(adj[x][a]!=Integer.MAX_VALUE&&adj[x][a]!=0){
edge[x][counter] = a;
counter++;
}
}
counter = 0;
}
int least = Integer.MAX_VALUE;
//Disjerta
int[] dist = new int[pastures];
final Comparator<Point> mine = new Comparator<Point>(){
public int compare(Point one, Point two){
if(one.y<two.y) return -1;
if(one.y>two.y) return 1;
else return 0;
}
};
PriorityQueue<Point> list = new PriorityQueue<Point>(pastures, mine);
int current;
//System.out.println("start");
for(int x = 0;x<loc.length;x++){//each cow pasture
//list.clear();
int start = loc[x];
dist[0] = Integer.MAX_VALUE;
past[0] = false;
for(int a = 1;a<pastures;a++){
dist[a] = adj[start][a];//clear dist log
list.add(new Point(a,dist[a]));
past[a] = false;
}
dist[start] = 0;// dist from start point
//begin
current = start;
//System.out.println("new");
top: while(true){
int dest = edge[current][0];
past[current]= true;
int a = 0;
while(dest!=-1){
if(dist[current]+adj[current][dest]<dist[dest]){
//list.remove(new Point(dest, dist[dest]));
dist[dest] = dist[current]+adj[current][dest];
adj[start][dest] = dist[dest];
list.add(new Point(dest, dist[dest]));
}
a++;
dest = edge[current][a];
}
while(past[current]){
if(list.size()==0) break top;
current = list.poll().x;;
}
}
//for(int b = 0;b<dist.length;b++) adj[start][b] = dist[b];
}
int temp = 0;
top: for(int x = 0;x<pastures;x++){
temp = 0;
for(int b = 0; b<cows;b++){
temp+=adj[loc[b]][x];
if(adj[loc[b]][x]==Integer.MAX_VALUE) continue top;
}
if(temp<least) least = temp;
}
out.println(least);
f.close();
out.close();
System.exit(0);
}
}