Skip to content
This repository was archived by the owner on Feb 29, 2024. It is now read-only.

Commit c8fcfac

Browse files
javaarchivejavaarchive
authored
Add files via upload
1 parent 0b3abab commit c8fcfac

File tree

1 file changed

+219
-166
lines changed

1 file changed

+219
-166
lines changed

‎dining.java‎

Lines changed: 219 additions & 166 deletions
Original file line numberDiff line numberDiff line change
@@ -1,167 +1,220 @@
1-
import java.io.*;
2-
import java.util.*;
3-
public class dining {
4-
public static int[] distTo;
5-
public static int[] distOrig;
6-
public static final int NO_PARENT = -1; // Constant for no parent
7-
public static void main(String[] args) throws IOException {
8-
BufferedReader f = new BufferedReader(new FileReader("dining.in"));
9-
StringTokenizer st = new StringTokenizer(f.readLine());
10-
int N,M,K;
11-
N = Integer.parseInt(st.nextToken());
12-
M = Integer.parseInt(st.nextToken());
13-
K = Integer.parseInt(st.nextToken());
14-
final int numOfCows = N - 1;
15-
List<List<Integer>> graph = new ArrayList<>(N);
16-
for(int i = 0; i < N; i ++) {
17-
graph.add(new ArrayList<>());
18-
}
19-
Map<Pair,Integer> cost = new HashMap<>();
20-
for(int i =0 ; i < M; i ++) {
21-
st = new StringTokenizer(f.readLine());
22-
int start = Integer.parseInt(st.nextToken());
23-
int end = Integer.parseInt(st.nextToken());
24-
int edgeCost = Integer.parseInt(st.nextToken());
25-
graph.get(start-1).add(end-1);
26-
graph.get(end-1).add(start-1);
27-
cost.put(new Pair(start-1,end-1), edgeCost);
28-
}
29-
Map<Pair,Integer> costWithHaybales = new HashMap<>(cost);
30-
System.out.println("Cost without haybales: "+cost);
31-
System.out.println("Graph as an edgelist: "+graph);
32-
int[] taste = new int[N];
33-
Pair key;
34-
//cost.get(new Pair(0,1));
35-
for(int i = 0; i < K; i ++) {
36-
st = new StringTokenizer(f.readLine());
37-
int index = Integer.parseInt(st.nextToken()) - 1;
38-
int value = Integer.parseInt(st.nextToken());
39-
//costWithHaybales.get(new Pair(0,1));
40-
for(int node: graph.get(index)) {
41-
key = new Pair(index,node);//assert key.equals(new Pair(node,index));
42-
//System.out.println("Map: "+costWithHaybales);
43-
//System.out.println(key+ " "+costWithHaybales.get(key));
44-
costWithHaybales.put(key,
45-
costWithHaybales.get(key) - value);
46-
}
47-
taste[index] = value;
48-
}
49-
System.out.println("Cost with haybales: "+costWithHaybales);
50-
f.close();
51-
int[] empty = new int[N];
52-
Arrays.fill(empty, Integer.MAX_VALUE);
53-
//distTo = new int[M];
54-
distTo= Arrays.copyOf(empty, N);
55-
distOrig= Arrays.copyOf(empty, N);
56-
Set<Integer> visited = new HashSet<>();
57-
PriorityQueue<Integer> nextNodes = new PriorityQueue<>(new Comparator<Integer>() {
58-
@Override
59-
public int compare(Integer arg0, Integer arg1) {
60-
return Integer.compare(dining.distTo[arg1], dining.distTo[arg0]);
61-
//return 0;
62-
}
63-
});
64-
nextNodes.add(N-1);
65-
// begin dijkstra from barn with haybales
66-
while(visited.size() < N) {
67-
System.out.println(visited.size());
68-
int u = nextNodes.remove(); // Get next node
69-
System.out.println(u);
70-
visited.add(u);
71-
List<Integer> adj = graph.get(u);
72-
for(int node:adj) {
73-
if(!visited.contains(node)) {
74-
int edgeDist = costWithHaybales.get(new Pair(u,node));
75-
int totalDist = distTo[u] + edgeDist;
76-
if (totalDist < distTo[node])
77-
distTo[node] = totalDist;
78-
nextNodes.add(node);
79-
}
80-
}
81-
}
82-
PriorityQueue<Integer> nextNodesOrig = new PriorityQueue<>(new Comparator<Integer>() {
83-
@Override
84-
public int compare(Integer arg0, Integer arg1) {
85-
return Integer.compare(dining.distOrig[arg1], dining.distOrig[arg0]);
86-
//return 0;
87-
}
88-
});
89-
visited.clear();
90-
nextNodesOrig.add(N-1);
91-
// begin dijkstra from barn without haybales
92-
while(visited.size() < N) {
93-
int u = nextNodesOrig.remove(); // Get next node
94-
visited.add(u);
95-
List<Integer> adj = graph.get(u);
96-
for(int node:adj) {
97-
if(!visited.contains(node)) {
98-
int edgeDist = cost.get(new Pair(u,node));
99-
int totalDist = distOrig[u] + edgeDist;
100-
if (totalDist < distOrig[node])
101-
distOrig[node] = totalDist;
102-
nextNodesOrig.add(node);
103-
}
104-
}
105-
}
106-
System.out.println("Output :" + Arrays.toString(distOrig));
107-
System.out.println("Output(haybales):" + Arrays.toString(distTo));
108-
109-
}
110-
}
111-
// Order does not matter pair
112-
class Pair{
113-
int x,y;
114-
public Pair(int x,int y) {
115-
this.x =x;
116-
this.y =y;
117-
}
118-
@Override
119-
public String toString() {
120-
return "("+this.x+","+this.y+")";
121-
}
122-
@Override
123-
public boolean equals(Object obj) {
124-
if(obj instanceof Pair) {
125-
Pair p = (Pair) obj;
126-
if((p.x == this.x && p.y == this.y) || (p.x == this.y && this.x == p.y)) {
127-
return true;
128-
}
129-
}else {
130-
return false;
131-
}
132-
return false;
133-
}
134-
@Override
135-
public int hashCode(){
136-
return (Integer.hashCode(this.x) + 3) * (Integer.hashCode(this.y) + 3);
137-
}
138-
}
139-
class Edge{
140-
int x;
141-
int y;
142-
int weight;
143-
public Edge(int x,int y,int weight) {
144-
this.x = x;
145-
this.y =y;
146-
this.weight = weight;
147-
}
148-
public String toString() {
149-
return "("+this.x+"--"+this.y+" = "+this.weight+")";
150-
}
151-
@Override
152-
public boolean equals(Object obj) {
153-
if(obj instanceof Edge) {
154-
Edge other = (Edge) obj;
155-
if((this.x == other.x && this.y == other.y) || (this.x == other.y && this.y == other.x)) {
156-
if(this.weight == other.weight) {
157-
return true;
158-
}else {
159-
return false;
160-
}
161-
}
162-
return false;
163-
}else {
164-
return false;
165-
}
166-
}
1+
import java.io.*;
2+
import java.util.*;
3+
public class dining {
4+
public static int[] distTo;
5+
public static int[] distOrig;
6+
public static final int NO_PARENT = -1; // Constant for no parent
7+
public static void main(String[] args) throws IOException {
8+
BufferedReader f = new BufferedReader(new FileReader("dining.in"));
9+
StringTokenizer st = new StringTokenizer(f.readLine());
10+
int N,M,K;
11+
N = Integer.parseInt(st.nextToken());
12+
M = Integer.parseInt(st.nextToken());
13+
K = Integer.parseInt(st.nextToken());
14+
final int numOfCows = N - 1;
15+
List<List<Integer>> graph = new ArrayList<>(N);
16+
for(int i = 0; i < N; i ++) {
17+
graph.add(new ArrayList<>());
18+
}
19+
Map<Pair,Integer> cost = new HashMap<>();
20+
for(int i =0 ; i < M; i ++) {
21+
st = new StringTokenizer(f.readLine());
22+
int start = Integer.parseInt(st.nextToken());
23+
int end = Integer.parseInt(st.nextToken());
24+
int edgeCost = Integer.parseInt(st.nextToken());
25+
graph.get(start-1).add(end-1);
26+
graph.get(end-1).add(start-1);
27+
cost.put(new Pair(start-1,end-1), edgeCost);
28+
}
29+
Map<Pair,Integer> costWithHaybales = new HashMap<>(cost);
30+
//System.out.println("Cost without haybales: "+cost);
31+
//System.out.println("Graph as an edgelist: "+graph);
32+
int[] taste = new int[N];
33+
Pair key;
34+
List<Integer> bales = new ArrayList<>();
35+
//Map<Integer, Integer> haybales = new HashMap<>();
36+
//cost.get(new Pair(0,1));
37+
for(int i = 0; i < K; i ++) {
38+
st = new StringTokenizer(f.readLine());
39+
int index = Integer.parseInt(st.nextToken()) - 1;
40+
bales.add(index);
41+
int value = Integer.parseInt(st.nextToken());
42+
43+
//costWithHaybales.get(new Pair(0,1));
44+
for(int node: graph.get(index)) {
45+
key = new Pair(index,node);//assert key.equals(new Pair(node,index));
46+
//System.out.println("Map: "+costWithHaybales);
47+
//System.out.println(key+ " "+costWithHaybales.get(key));
48+
//costWithHaybales.put(key,
49+
// costWithHaybales.get(key) - value);
50+
}
51+
taste[index] = value;
52+
}
53+
//System.out.println("Cost with haybales: "+costWithHaybales);
54+
f.close();
55+
int[] empty = new int[N];
56+
Arrays.fill(empty, Integer.MAX_VALUE);
57+
empty[N-1] = 0;
58+
//distTo = new int[M];
59+
//distTo= Arrays.copyOf(empty, N);
60+
distOrig= Arrays.copyOf(empty, N);
61+
Set<Integer> visited = new HashSet<>();
62+
PriorityQueue<Integer> nextNodes = new PriorityQueue<>(new Comparator<Integer>() {
63+
@Override
64+
public int compare(Integer arg0, Integer arg1) {
65+
return Integer.compare(dining.distTo[arg1], dining.distTo[arg0]);
66+
//return 0;
67+
}
68+
});
69+
/*
70+
nextNodes.add(N-1);
71+
// begin dijkstra from barn with haybales
72+
while(visited.size() < N) {
73+
System.out.println(visited.size());
74+
int u = nextNodes.remove(); // Get next node
75+
System.out.println(u);
76+
visited.add(u);
77+
List<Integer> adj = graph.get(u);
78+
for(int node:adj) {
79+
if(!visited.contains(node)) {
80+
int edgeDist = costWithHaybales.get(new Pair(u,node));
81+
int totalDist = distTo[u] + edgeDist;
82+
if (totalDist < distTo[node])
83+
distTo[node] = totalDist;
84+
nextNodes.add(node);
85+
}
86+
}
87+
}
88+
*/
89+
PriorityQueue<Integer> nextNodesOrig = new PriorityQueue<>(new Comparator<Integer>() {
90+
@Override
91+
public int compare(Integer arg0, Integer arg1) {
92+
return Integer.compare(dining.distOrig[arg1], dining.distOrig[arg0]);
93+
//return 0;
94+
}
95+
});
96+
//visited.clear();
97+
98+
nextNodesOrig.add(N-1);
99+
// begin dijkstra from barn without haybales
100+
while(visited.size() < N) {
101+
int u = nextNodesOrig.remove(); // Get next node
102+
visited.add(u);
103+
List<Integer> adj = graph.get(u);
104+
for(int node:adj) {
105+
if(!visited.contains(node)) {
106+
int edgeDist = cost.get(new Pair(u,node));
107+
int totalDist = distOrig[u] + edgeDist;
108+
if (totalDist < distOrig[node])
109+
distOrig[node] = totalDist;
110+
nextNodesOrig.add(node);
111+
}
112+
}
113+
}
114+
//System.out.println("Output :" + Arrays.toString(distOrig));
115+
116+
//for(int bale: graph.get(N-1)) {
117+
// graph.get(bale).remove((Object) (N-1));
118+
//}
119+
120+
//graph.get(N-1).clear();
121+
122+
for(int i = 0 ; i < K; i++) {
123+
int target = bales.get(i);
124+
//for(int bale:graph.get(target)) {
125+
// graph.get(bale).remove(target);
126+
//}
127+
//graph.get(target).clear();
128+
graph.get(target).add(N-1);
129+
graph.get(N-1).add(target);
130+
costWithHaybales.put(new Pair(target,N-1), distOrig[target] - taste[i]);
131+
}
132+
visited.clear();
133+
distTo= Arrays.copyOf(empty, N);
134+
nextNodes.add(N-1);
135+
// begin dijkstra from barn with haybales
136+
while(visited.size() < N) {
137+
//System.out.println(visited.size());
138+
int u = nextNodes.remove(); // Get next node
139+
//System.out.println(u);
140+
visited.add(u);
141+
List<Integer> adj = graph.get(u);
142+
for(int node:adj) {
143+
if(!visited.contains(node)) {
144+
int edgeDist = costWithHaybales.get(new Pair(u,node));
145+
int totalDist = distTo[u] + edgeDist;
146+
if (totalDist < distTo[node])
147+
distTo[node] = totalDist;
148+
nextNodes.add(node);
149+
}
150+
}
151+
}
152+
//System.out.println("Output(haybales):" + Arrays.toString(distTo));
153+
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("dining.out")));
154+
for(int i =0 ; i < numOfCows; i ++) {
155+
if(distTo[i] <= distOrig[i]) {
156+
pw.println(1);
157+
}else {
158+
pw.println(0);
159+
}
160+
}
161+
pw.close();
162+
}
163+
}
164+
// Order does not matter pair
165+
class Pair{
166+
int x,y;
167+
public Pair(int x,int y) {
168+
this.x =x;
169+
this.y =y;
170+
}
171+
@Override
172+
public String toString() {
173+
return "("+this.x+","+this.y+")";
174+
}
175+
@Override
176+
public boolean equals(Object obj) {
177+
if(obj instanceof Pair) {
178+
Pair p = (Pair) obj;
179+
if((p.x == this.x && p.y == this.y) || (p.x == this.y && this.x == p.y)) {
180+
return true;
181+
}
182+
}else {
183+
return false;
184+
}
185+
return false;
186+
}
187+
@Override
188+
public int hashCode(){
189+
return (Integer.hashCode(this.x) + 3) * (Integer.hashCode(this.y) + 3);
190+
}
191+
}
192+
class Edge{
193+
int x;
194+
int y;
195+
int weight;
196+
public Edge(int x,int y,int weight) {
197+
this.x = x;
198+
this.y =y;
199+
this.weight = weight;
200+
}
201+
public String toString() {
202+
return "("+this.x+"--"+this.y+" = "+this.weight+")";
203+
}
204+
@Override
205+
public boolean equals(Object obj) {
206+
if(obj instanceof Edge) {
207+
Edge other = (Edge) obj;
208+
if((this.x == other.x && this.y == other.y) || (this.x == other.y && this.y == other.x)) {
209+
if(this.weight == other.weight) {
210+
return true;
211+
}else {
212+
return false;
213+
}
214+
}
215+
return false;
216+
}else {
217+
return false;
218+
}
219+
}
167220
}

0 commit comments

Comments
 (0)