We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Jeanie's Route
  5. Discussions

Jeanie's Route

Sort by

recency

|

28 Discussions

|

  • diosilvapy
     + 0 comments

    A questão apresentada descreve um problema de roteamento em um grafo ponderado, onde Jeanie, uma carteira, precisa entregar cartas em diferentes cidades de Byteland. O objetivo é encontrar a distância mínima que Jeanie precisa percorrer para entregar todas as cartas.

    POREM SOMENTE COMPILA ERRO :

    import math import os import sys import itertools

    def min_delivery_distance(n, letters, roads): # Construir o grafo (lista de adjacências) graph = [[] for _ in range(n)] for u, v, w in roads: graph[u - 1].append((v - 1, w)) graph[v - 1].append((u - 1, w))

    # Função DFS para calcular distâncias
def dfs(start, end, visited, current_dist):
    if start == end:
        return current_dist
    visited[start] = True
    min_dist = float('inf')
    for neighbor, weight in graph[start]:
        if not visited[neighbor]:
            new_dist = dfs(neighbor, end, visited[:], current_dist + weight)
            min_dist = min(min_dist, new_dist)
    return min_dist

# Calcular distâncias entre todas as cidades de entrega
dist = {}
for i in range(len(letters)):
    for j in range(i + 1, len(letters)):
        start = letters[i] - 1
        end = letters[j] - 1
        visited = [False] * n
        distance = dfs(start, end, visited, 0)
        dist[(letters[i], letters[j])] = distance
        dist[(letters[j], letters[i])] = distance

# Gerar todas as permutações e calcular a distância mínima
min_distance = float('inf')
for permutation in itertools.permutations(letters):
    current_distance = 0
    for i in range(len(permutation) - 1):
        current_distance += dist[(permutation[i], permutation[i + 1])]
    min_distance = min(min_distance, current_distance)

return min_distance

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n, k = map(int, input().rstrip().split())
letters = list(map(int, input().rstrip().split()))
roads = []
for _ in range(n - 1):
    roads.append(list(map(int, input().rstrip().split())))

result = min_delivery_distance(n, letters, roads)

fptr.write(str(result) + '\n')
fptr.close()

  • khteh
     + 1 comment

    How could the editorial solve the problem with cities={2, 3} and roads={{1, 2, 1}, {1, 3, 3}, {2, 4, 2}, {3, 4, 4}}? It's a 4-node graph connected in a circle. The editorial would return 20-9=11 instead of the expected result of 4?

  • shanefostersmith
     + 0 comments

    Java solution. First, remove outer, non-letter cities (will never be visited). Then, from the (new) outer letter cities, go inward until you reach an intersection city (3 or more edges) and calculate the minimum and maximum subtree value. You can consider a 'minimum' subtree is where you start or end a path at that subtree. A maximum subtree will double value of all "lines" in the subtree. Eventually, you will reach an inner city in which all subtrees are calculated. From there you can calculate an intersection's cities minimum path will add two minimum subtrees with the rest as maximum subtrees. Once you've reached the most inner intersection city, you can calculate it's minimum path and move back outerwards to calcuate the rest of the intersections minimum paths (with optimizations). One of the intersections will have the minimum path, and that's what you will return. Minimum is O(# cities), maximum is O(# cities + # edges).

    static int jeanisRoute(int[] k, int[][] roads) {
        int biggestCity = roads.length + 1;
        // Trivial Cases
        if (biggestCity == 2) {
            return roads[0][2];
        }
        if (biggestCity == 3 && k.length == 3 ) {
            int sum = 0;
            for (int i = 0; i < 2; i++) {
                sum += roads[i][2];
            }
            return sum;
        }
        Set<Integer> letterCities = new HashSet<>();
        for (int i = 0; i < k.length; i++) {
            letterCities.add(k[i]);
        }
        Map<Integer,List<Integer>> adjList = new HashMap<>();
        Map<Edge,Integer> weights = new HashMap<>();
        // Create adjacency list
        for (int i = 1; i <= biggestCity; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int i = 0; i < roads.length; i++) {
            int[] currRoad = roads[i];
            int vertex1 = currRoad[0];
            int vertex2 = currRoad[1];
            adjList.get(vertex1).add(vertex2);
            adjList.get(vertex2).add(vertex1);
            Edge newEdge = new Edge(vertex1,vertex2);
            weights.put(newEdge,currRoad[2]);
        }
        if (biggestCity == 3) {
            int sum = 0;
            for (int i = 0; i < k.length; i++) {
                List<Integer> connected = adjList.get(k[i]);
                if (connected.size() == 1) {
                    int connectedCity = connected.get(0);
                    Edge newEdge = new Edge(k[i],connectedCity);
                    if (letterCities.contains(connectedCity)) {
                        return weights.get(newEdge);
                    } else {
                        sum += weights.get(newEdge);
                    }
                }
            }
            return sum;
        }
        int citiesLeft = biggestCity;
        Set<Integer> outerCities = new HashSet<>();
        
        // Remove non-letter cities that will never be visited (outer of graph)
        // Create set of "outer cities"
        for (int i = 1; i <= biggestCity; i++) {
            List<Integer> connectedCities = adjList.get(i);
            if (connectedCities.size() != 1) {
                continue;
            }
            if (letterCities.contains(i)) {
                outerCities.add(i);
            } else { // Current City will never be visited
                int currCity = i;
                while (true) {
                    int adjCity = adjList.get(currCity).get(0);
                    adjList.get(currCity).remove(0);
                    List<Integer> connectedToAdj = adjList.get(adjCity);
                    for (int j = 0; j < connectedToAdj.size(); j++) {
                        if (connectedToAdj.get(j) == currCity) {
                            connectedToAdj.remove(j);
                            break;
                        }
                    }
                    citiesLeft--;
                    if (adjCity > i || connectedToAdj.size() != 1) {
                        break;
                    }
                    if (letterCities.contains(adjCity)) {
                        outerCities.add(adjCity);
                        break;
                    }
                    currCity = adjCity;
                }
            }
        }
        
        // For every 'intersection' can choose two subtrees to be minimum and 
        // rest be maximum. Choose intersection that is minimal. 
        Map<Integer, int[][]> interToMinMaxSubtrees = new HashMap<>();
        Map<Integer, Integer> interMaxTotal = new HashMap<>();
        Map<Integer, int[]> interDiffMaxMin = new HashMap<>();
        Map<Integer, Set<Integer>> interToVisitedEdges = new HashMap<>();
        Map<Integer, Integer> interNumTreesCalculated = new HashMap<>();
        int noIntersection = 0;
        Set<Integer> nextCities = new HashSet<>();
        // Start with Outer Cities to Intersection Cities
        for (int outer : outerCities) {
            System.out.println("Curr Outer: " + outer);
            citiesLeft--;
            int prevCity = outer;
            int currCity = adjList.get(outer).get(0);
            int currLen = weights.get(new Edge(prevCity,currCity));
            while (true) {
                List<Integer> connectedToCurr = adjList.get(currCity);
                int numConnected = connectedToCurr.size();
                if (numConnected > 2) { // Found intersection city
                    // Find edge index it currently intersected with
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    // Update maps
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    int[][] minMax = interToMinMaxSubtrees.computeIfAbsent(currCity, key ->
                    new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currLen;
                    minMax[edgeIntersect][1] = 2*currLen; 
                    
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + minMax[edgeIntersect][1]);
                    
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    interNumTreesCalculated.put(currCity, edgesSeen);
                    
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    if (edgesSeen == numConnected - 1) {
                        nextCities.add(currCity);
                    }
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (currLen < currLargest[0]) {
                        break;
                    }
                    if (currLen > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = currLen;
                    } else {
                        currLargest[0] = currLen;
                    }
                    break;
                }
                // This city is part of a 'line'
                if (numConnected == 2) {
                    citiesLeft--;
                    int nextCity = connectedToCurr.get(0) == prevCity ? 
                    connectedToCurr.get(1) : connectedToCurr.get(0);
                    currLen += weights.get(new Edge(currCity, nextCity));
                    prevCity = currCity;
                    currCity = nextCity;
                    continue;
                }
                // Went from outer city to outer city, no intersections
                noIntersection = currLen;
                break;
            }
            if (noIntersection > 0) {
                return noIntersection;
            }
        }
        // Only one intersection
        if (citiesLeft == 1) {
            int intersection = (int) interMaxTotal.keySet().toArray()[0];
            int[] largestSubTrees = interDiffMaxMin.get(intersection);
            int result = interMaxTotal.get(intersection) - 
            largestSubTrees[0] - largestSubTrees[1];
            return result;
        }
        Queue<Integer> toCalculate = new LinkedList<>();
        Map<Integer,int[][]> interToInterCityAndLen = new HashMap<>();
        
        int totalMax = 0;
        boolean[] calculated = new boolean[biggestCity];
        while (true) {
            Set<Integer> newCities = new HashSet<>();
            for (int inter : nextCities) {
                List<Integer> connectedToInter = adjList.get(inter);
                Set<Integer> edgesVisited = interToVisitedEdges.get(inter);
                if (edgesVisited.size() == connectedToInter.size()) {
                    continue;
                }
                int prevCity = inter;
                int lineStartIdx = 0;
                int currCity = 0;
                for (int i = 0; i < connectedToInter.size(); i++) {
                    if (!edgesVisited.contains(i)) {
                        currCity = connectedToInter.get(i);
                        lineStartIdx = i;
                        break;
                    }
                }
                
                // If intersection to intersection already calculated
                if (interToInterCityAndLen.get(inter) != null && interToInterCityAndLen.get(inter)[lineStartIdx][0] != 0) {
                    continue;
                }
                int currLen = weights.get(new Edge(prevCity,currCity));
                while (true) {
                    List<Integer> connectedToCurr = adjList.get(currCity);
                    int numConnected = connectedToCurr.size();
                    
                    // This city is part of a 'line'
                    if (numConnected == 2) {
                        int nextCity = connectedToCurr.get(0) == prevCity ? 
                        connectedToCurr.get(1) : connectedToCurr.get(0);
                        currLen += weights.get(new Edge(currCity,nextCity));
                        prevCity = currCity;
                        currCity = nextCity;
                        continue;
                    }
                    // Found intersection
                    
                    // Find edge index that was intersected
                    int edgeIntersect = 0;
                    for (int i = 0; i < numConnected; i++) {
                        int connectedCity = connectedToCurr.get(i);
                        if (connectedCity == prevCity) {
                            edgeIntersect = i;
                            break;
                        }
                    }
                    interToVisitedEdges.computeIfAbsent(currCity, 
                    key -> new HashSet<>()).add(edgeIntersect);
                    
                    // Update intersection connections
                    int[] connectCurrToInter = {currCity,edgeIntersect,currLen};
                    int[] connectInterToCurr = {inter,lineStartIdx,currLen};
                    interToInterCityAndLen.computeIfAbsent(currCity, 
                    key -> new int[numConnected][3])[edgeIntersect] = connectInterToCurr;
                    interToInterCityAndLen.computeIfAbsent(inter, 
                    key -> new int[numConnected][3])[lineStartIdx] = connectCurrToInter;
                    
                    // Find min and max of current subtree
                    int previousMax = interMaxTotal.get(inter);
                    int prevLargestSubTree = interDiffMaxMin.get(inter)[1];
                    int previousMin = interMaxTotal.get(inter) - prevLargestSubTree;
                    int currentMax =  2*currLen + previousMax;
                    int currentMin = previousMin + currLen;
                    int diffMaxMin = currentMax - currentMin;
                    
                    // Update maps
                    interMaxTotal.put(currCity, 
                    interMaxTotal.getOrDefault(currCity, 0) + currentMax);
                    
                    int minMax[][] = interToMinMaxSubtrees.computeIfAbsent(currCity ,
                    key -> new int[numConnected][2]);
                    minMax[edgeIntersect][0] = currentMin;
                    minMax[edgeIntersect][1] = currentMax;
                    
                    interNumTreesCalculated.put(currCity, 
                    interNumTreesCalculated.getOrDefault(currCity, 0) + 1);
                    interDiffMaxMin.computeIfAbsent(currCity, 
                    key -> new int[2]);
                    int[] currLargest = interDiffMaxMin.get(currCity);
                    if (diffMaxMin > currLargest[1]) {
                        currLargest[0] = currLargest[1];
                        currLargest[1] = diffMaxMin;
                    } else if (diffMaxMin > currLargest[0]) {
                        currLargest[0] = diffMaxMin;
                    }
                    int edgesSeen = interToVisitedEdges.get(currCity).size();
                    if (edgesSeen == numConnected - 1) {
                        newCities.add(currCity);
                    } else if (edgesSeen == numConnected) {
                        newCities.remove(currCity);
                        if (interNumTreesCalculated.get(currCity) == numConnected) {
                            totalMax = interMaxTotal.get(currCity);
                            toCalculate.add(currCity);
                        }
                    }
                    break;
                } // while loop inner end
            } // for loop end
            if (newCities.isEmpty()) {
                break;
            } 
            nextCities = newCities;
        }
        
        int minSeen = Integer.MAX_VALUE;
        // only visit intersections where all subtrees have been calculated
        while (!toCalculate.isEmpty()) {
            int currInter = toCalculate.poll();
            if (calculated[currInter - 1]) {
                continue;
            }
            // Calculate minimum path for this city
            calculated[currInter - 1] = true;
            int[] currLargest = interDiffMaxMin.get(currInter);
            int result = totalMax - currLargest[1] - currLargest[0];
            if (result < minSeen) {
                minSeen = result;
            }
            // Calculate subtree for neighboring city
            int[][] connectedToCurr = interToInterCityAndLen.get(currInter);
            for (int i = 0; i < connectedToCurr.length; i++) {
                int connectedCity = connectedToCurr[i][0];
                if (connectedCity == 0 || calculated[connectedCity - 1]) {
                    continue;
                }
                int numSubTreesTotal = adjList.get(connectedCity).size();
                int numSubTreesCalculated = interNumTreesCalculated.get(connectedCity);
                int treesLeft= numSubTreesTotal - numSubTreesCalculated;
                if (treesLeft == 0) {
                    continue;
                }
                // Calculate subtree from connected to current
                int connectedLen = connectedToCurr[i][2];
                int[][] currMaxMin = interToMinMaxSubtrees.get(currInter);
                int maxRemoved = currMaxMin[i][1];
                int minRemoved = currMaxMin[i][0];
                int diffRemoved = maxRemoved - minRemoved;
                int connectedMaxSubTree = totalMax - maxRemoved + 2*connectedLen;
                int connectedMinSubTree;
                if (diffRemoved < currLargest[1]) {
                    connectedMinSubTree = connectedMaxSubTree - currLargest[1];
                }
                else  {
                    connectedMinSubTree= connectedMaxSubTree - currLargest[0];
                }
                connectedMinSubTree += connectedLen;
                int connectedDiff = connectedMaxSubTree - connectedMinSubTree;
                int[] largestDiffs = interDiffMaxMin.get(connectedCity);
                if (connectedDiff > largestDiffs[1]) {
                    largestDiffs[0] = largestDiffs[1];
                    largestDiffs[1] = connectedDiff;
                } else if (connectedDiff > largestDiffs[0]) {
                    largestDiffs[0] = connectedDiff;
                }
                // This city will never be the minimum
                if (largestDiffs[1] + largestDiffs[0] <= currLargest[1] + currLargest[0]) {
                    continue;
                }
                // Update maps for connected
                interNumTreesCalculated.put(connectedCity,++numSubTreesCalculated);
                if (--treesLeft == 0) {
                    toCalculate.add(connectedCity);
                } 
                int subTreeIdx = connectedToCurr[i][1];
                int[][] connectedMinMax = interToMinMaxSubtrees.get(connectedCity);
                connectedMinMax[subTreeIdx][0] = connectedMinSubTree;
                connectedMinMax[subTreeIdx][1] = connectedMaxSubTree;
            }
        }
        return minSeen;
    }

  • callummequigley
     + 1 comment

    python3

    def jeanisRoute(n, cities, roads):
    """The strategy of this approach is to:
    1) Prune off any branches of the tree that aren't visited
    2) Note that to visit each remaining node and return to start
    has length = 2 * sum(all remaining edge weights)
    3) Since we need not return to start, the most by which we can
    reduce total length is the max distance b/w 2 nodes
    i.e. the tree's diameter."""
    
    # Make the adjacency list and sum (2x) total graph weight
    adj = {i: [] for i in range(1, n+1)}
    total = 0
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
        total += 2*w
    
    # Iteratively, prune leaves that are not visited (adjusting total)
    flag = True  # track if any changes made this pass
    non_dest = set(range(1, n+1)).difference({*cities})
    while flag:
        flag = False
        for u in non_dest:
            if len(adj[u]) == 1:
                v, w = adj[u].pop()
                adj[v].remove((u, w))
                flag = True
                total -= 2*w
                
    # Compute the pruned tree's diameter by running DFS twice.
    # First time, start at any city and find the furthest leaf.
    # Second time, start at first endpoint. Result is the diameter
    u, d = dfs(cities[0], adj)
    v, diameter = dfs(u, adj)
    
    return total - diameter
        

def dfs(start, adj):
    "Conduct DFS to find the node of max distance from node <start>"
    
    seen = set([start])
    queue = [(start, 0)]
    end, max_dist = start, 0
    
    while queue:
        curr, dist = queue.pop()
        for nxt, wt in adj[curr]:
            if nxt not in seen:
                seen.add(nxt)
                new_dist = dist + wt
                queue.append((nxt, new_dist))
                if new_dist > max_dist:
                    end, max_dist = nxt, new_dist
    
    return end, max_dist

  • gjtnwjd40
     + 0 comments

    how can we know which city is must delivered or not ?? The thing we could know is the number of letter.. isn't it??