Untitled

 avatar
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