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

Commit c52d26e

Browse files
javaarchivejavaarchive
committed
Update dining.java
1 parent 3bcb878 commit c52d26e

File tree

1 file changed

+40
-61
lines changed

1 file changed

+40
-61
lines changed

‎dining.java‎

Lines changed: 40 additions & 61 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,38 @@
11
import java.io.*;
22
import java.util.*;
33
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
4+
5+
public static int[] dijkstra(Map<Pair, Integer> cost, List<List<Integer>> graph, final int N) {
6+
int[] dist = new int[N];
7+
Set<Integer> visited = new HashSet<>();
8+
PriorityQueue<Integer> nodeQueue = new PriorityQueue<>(new Comparator<Integer>() {
9+
@Override
10+
public int compare(Integer arg0, Integer arg1) {
11+
return Integer.compare(dist[arg0], dist[arg1]);
12+
//return 0;
13+
}
14+
});
15+
Arrays.fill(dist, Integer.MAX_VALUE);
16+
dist[N-1] = 0; // Starting value
17+
nodeQueue.add(N-1);
18+
while(visited.size() < N) {
19+
int u = nodeQueue.remove(); // Get next node
20+
visited.add(u);
21+
List<Integer> adj = graph.get(u);
22+
for(int node:adj) {
23+
if(!visited.contains(node)) {
24+
int edgeDist = cost.get(new Pair(u,node));
25+
int totalDist = dist[u] + edgeDist;
26+
if (totalDist < dist[node])
27+
dist[node] = totalDist;
28+
nodeQueue.add(node);
29+
}
30+
}
31+
}
32+
return dist;
33+
}
734
public static void main(String[] args) throws IOException {
8-
BufferedReader f = new BufferedReader(new FileReader("dining.in"));
35+
BufferedReader f = new BufferedReader(new FileReader("2.in"));
936
StringTokenizer st = new StringTokenizer(f.readLine());
1037
int N,M,K;
1138
N = Integer.parseInt(st.nextToken());
@@ -28,7 +55,7 @@ public static void main(String[] args) throws IOException {
2855
}
2956
Map<Pair,Integer> costWithHaybales = new HashMap<>(cost);
3057
//System.out.println("Cost without haybales: "+cost);
31-
//System.out.println("Graph as an edgelist: "+graph);
58+
System.out.println("Graph as an edgelist: "+graph);
3259
int[] taste = new int[N];
3360
//Pair key;
3461
List<Integer> bales = new ArrayList<>();
@@ -58,15 +85,7 @@ public static void main(String[] args) throws IOException {
5885
empty[N-1] = 0;
5986
//distTo = new int[M];
6087
//distTo= Arrays.copyOf(empty, N);
61-
distOrig= Arrays.copyOf(empty, N);
62-
Set<Integer> visited = new HashSet<>();
63-
PriorityQueue<Integer> nextNodes = new PriorityQueue<>(new Comparator<Integer>() {
64-
@Override
65-
public int compare(Integer arg0, Integer arg1) {
66-
return Integer.compare(dining.distTo[arg0], dining.distTo[arg1]);
67-
//return 0;
68-
}
69-
});
88+
int[] distOrig,distTo;
7089
/*
7190
nextNodes.add(N-1);
7291
// begin dijkstra from barn with haybales
@@ -87,32 +106,8 @@ public int compare(Integer arg0, Integer arg1) {
87106
}
88107
}
89108
*/
90-
PriorityQueue<Integer> nextNodesOrig = new PriorityQueue<>(new Comparator<Integer>() {
91-
@Override
92-
public int compare(Integer arg0, Integer arg1) {
93-
return Integer.compare(dining.distOrig[arg0], dining.distOrig[arg1]);
94-
//return 0;
95-
}
96-
});
97-
//visited.clear();
98109

99-
nextNodesOrig.add(N-1);
100-
// begin dijkstra from barn without haybales
101-
while(visited.size() < N) {
102-
int u = nextNodesOrig.remove(); // Get next node
103-
visited.add(u);
104-
List<Integer> adj = graph.get(u);
105-
for(int node:adj) {
106-
if(!visited.contains(node)) {
107-
int edgeDist = cost.get(new Pair(u,node));
108-
int totalDist = distOrig[u] + edgeDist;
109-
if (totalDist < distOrig[node])
110-
distOrig[node] = totalDist;
111-
nextNodesOrig.add(node);
112-
}
113-
}
114-
}
115-
//System.out.println("Output :" + Arrays.toString(distOrig));
110+
distOrig = dijkstra(cost, graph, N);
116111

117112
//for(int bale: graph.get(N-1)) {
118113
// graph.get(bale).remove((Object) (N-1));
@@ -130,30 +125,14 @@ public int compare(Integer arg0, Integer arg1) {
130125
graph.get(N-1).add(target);
131126
costWithHaybales.put(new Pair(target,N-1), distOrig[target] - taste[i]);
132127
}
133-
visited.clear();
134-
distTo= Arrays.copyOf(empty, N);
135-
nextNodes.add(N-1);
136-
// begin dijkstra from barn with haybales
137-
while(visited.size() < N) {
138-
//System.out.println(visited.size());
139-
int u = nextNodes.remove(); // Get next node
140-
//System.out.println(u);
141-
visited.add(u);
142-
List<Integer> adj = graph.get(u);
143-
for(int node:adj) {
144-
if(!visited.contains(node)) {
145-
int edgeDist = costWithHaybales.get(new Pair(u,node));
146-
int totalDist = distTo[u] + edgeDist;
147-
if (totalDist < distTo[node])
148-
distTo[node] = totalDist;
149-
nextNodes.add(node);
150-
}
151-
}
152-
}
153-
//System.out.println("Output(haybales):" + Arrays.toString(distTo));
128+
System.out.println("Cost : "+cost);
129+
System.out.println("Cost with haybales: "+costWithHaybales);
130+
distTo = dijkstra(costWithHaybales, graph, N);
131+
System.out.println("Output :" + Arrays.toString(distOrig));
132+
System.out.println("Output(haybales):" + Arrays.toString(distTo));
154133
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("dining.out")));
155134
for(int i =0 ; i < numOfCows; i ++) {
156-
if(distTo[i] >= distOrig[i]) {
135+
if(distTo[i] <= distOrig[i]) {
157136
pw.println(1);
158137
}else {
159138
pw.println(0);

0 commit comments

Comments
 (0)