GeezerVison is showing github.com — Java/dining.java at master · javaarchive/Java

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

Expand file tree

dining.java

Copy path

More file actions

Latest commit

History

135 lines (134 loc) · 4.32 KB

dining.java

Copy path

File metadata and controls

135 lines (134 loc) · 4.32 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.io.*;

import java.util.*;

public class dining {

public static int[] dijkstra(Map<Pair, Integer> cost, List<List<Integer>> graph, final int N, int source) {

int[] dist = new int[N];

PriorityQueue<Integer> visited = new PriorityQueue<>(N,new Comparator<Integer>() {

@Override

public int compare(Integer arg0, Integer arg1) {

return Integer.compare(dist[arg0], dist[arg1]);

//return 0;

}

});

Arrays.fill(dist, Integer.MAX_VALUE);

dist[N-1] = 0; // Starting value

//nodeQueue.add(N-1);

visited.add(source);

int u;

while(!visited.isEmpty()) {

//int u = nodeQueue.remove(); // Get next node

u = visited.remove();

List<Integer> adj = graph.get(u);

for(int node:adj) {

//if(dist[node] == Integer.MAX_VALUE)

{ // If this node has not been visited yet

int edgeDist = cost.get(new Pair(u,node));

int totalDist = dist[u] + edgeDist;

if (totalDist < dist[node])

{

dist[node] = totalDist;

visited.add(node);

}

//nodeQueue.add(node);

}

return dist;

}

public static void main(String[] args) throws IOException {

BufferedReader f = new BufferedReader(new FileReader("1.in"));

StringTokenizer st = new StringTokenizer(f.readLine());

int N,M,K;

N = Integer.parseInt(st.nextToken());

M = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

final int numOfCows = N - 1;

List<List<Integer>> graph = new ArrayList<>(M+1);

for(int i = 0; i < M+1; i ++) {

graph.add(new ArrayList<>());

}

Map<Pair,Integer> cost = new HashMap<>();

for(int i =0 ; i < M; i ++) {

st = new StringTokenizer(f.readLine());

int start = Integer.parseInt(st.nextToken());

int end = Integer.parseInt(st.nextToken());

int edgeCost = Integer.parseInt(st.nextToken());

graph.get(start-1).add(end-1);

graph.get(end-1).add(start-1);

cost.put(new Pair(start-1,end-1), edgeCost);

cost.put(new Pair(end-1,start-1), edgeCost);

}

//System.out.println("Cost : "+cost);

Map<Pair,Integer> costWithHaybales = new HashMap<>(cost);

System.out.println("Graph as an edgelist: "+graph);

int[] taste = new int[K];

List<Integer> bales = new ArrayList<>();

for(int i = 0; i < K; i ++) {

st = new StringTokenizer(f.readLine());

int index = Integer.parseInt(st.nextToken()) - 1;

bales.add(index);

int value = Integer.parseInt(st.nextToken());

taste[i] = value;

}

f.close();

//int[] empty = new int[N];

//Arrays.fill(empty, Integer.MAX_VALUE);

//empty[N-1] = 0;

int[] distOrig,distTo;

distOrig = dijkstra(cost, graph, N, N - 1);

//for(int bale: graph.get(N-1)) {

// graph.get(bale).remove((Object) (N-1));

//}

//graph.get(N-1).clear();

for(int i = 0 ; i < K; i++) {

int target = bales.get(i);

graph.get(target).add(N);

graph.get(N).add(target);

//System.out.println("Dist: "+distOrig[target]+" Taste: "+taste[i]);

//System.out.println(target+" -- "+(N-1) + " connected with weight "+(distOrig[target] - taste[i]));

costWithHaybales.put(new Pair(target,N), distOrig[target] - taste[i]);

//costWithHaybales.put(new Pair(N,target), distOrig[target] - taste[i]);

}

//System.out.println("Modified New Graph : "+graph);

System.out.println("Cost : "+cost);

System.out.println("Cost with haybales: "+costWithHaybales);

distTo = dijkstra(costWithHaybales, graph, N+1, N);

System.out.println("Output :" + Arrays.toString(distOrig));

System.out.println("Output(haybales):" + Arrays.toString(distTo));

PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("dining.out")));

for(int i =0 ; i < numOfCows; i ++) {

if(distTo[i] <= distOrig[i]) {

pw.println(1);

}else {

pw.println(0);

}

pw.close();

}

// Order does matter pair

class Pair{

int x,y;

public Pair(int x,int y) {

this.x =x;

this.y =y;

}

@Override

public String toString() {

return "("+this.x+","+this.y+")";

}

@Override

public boolean equals(Object obj) {

if(obj instanceof Pair) {

Pair p = (Pair) obj;

if((p.x == this.x && p.y == this.y)) {

return true;

}

return false;

}

@Override

public int hashCode(){

return Integer.hashCode(this.x) * (Integer.hashCode(this.y)+1);

}