Untitled
unknown
plain_text
a year ago
3.0 kB
8
Indexable
package DeliveryRobot; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class UserSolution { private City[] cities; private int answer; public void init(int N, int E, int[] sCity, int[] eCity, int[] mTime) { cities = new City[N]; for (int i = 0; i < N; i++) { cities[i] = new City(i); } for (int i = 0; i < E; i++) { add(sCity[i], eCity[i], mTime[i]); } } public void add(int sCity, int eCity, int mTime) { Node road = new Node(cities[eCity], mTime); cities[sCity].roads.add(road); } public int deliver(int mPos, int M, int[] mSender, int[] mReceiver) { dijkstra(cities[mPos]); for (int i = 0; i < M; i++) dijkstra(cities[mSender[i]]); for (int i = 0; i < M; i++) dijkstra(cities[mReceiver[i]]); answer = Integer.MAX_VALUE; deliver(cities[mPos], mSender, mReceiver, new boolean[M], 0); return answer; } private void deliver(City city, int[] senders, int[] receivers, boolean[] visited, int time) { if (time >= answer) return; boolean flag = true; for (int i = 0; i < visited.length; i++) { if (visited[i]) continue; flag = false; visited[i] = true; int x = time + city.distances[senders[i]] + cities[senders[i]].distances[receivers[i]]; deliver(cities[receivers[i]], senders, receivers, visited, x); visited[i] = false; } if (flag && time < answer) { answer = time; } } private void dijkstra(City city) { int[] distances = new int[cities.length]; city.distances = distances; Arrays.fill(distances, 1000000); distances[city.id] = 0; PriorityQueue<Node> queue = new PriorityQueue<>(); queue.add(new Node(city, 0)); while (!queue.isEmpty()) { Node node = queue.poll(); if (node.time > distances[node.city.id]) continue; for (Node road : node.city.roads) { int distance = node.time + road.time; if (distances[road.city.id] <= distance) continue; distances[road.city.id] = distance; queue.add(new Node(road.city, distance)); } } } private class City { public int id; public ArrayList<Node> roads = new ArrayList<>(); public int[] distances; public City(int id) { this.id = id; } } private class Node implements Comparable<Node> { public City city; public int time; public Node(City city, int time) { this.city = city; this.time = time; } @Override public int compareTo(Node o) { return time - o.time; } } }
Editor is loading...
Leave a Comment