Freaks City

Problem Overview Given a graph with (n) intersections ((n \le 10^3)) and (m) bidirectional roads ((m \le 10^4)), a person named T moves first along a predetermined path (c_1, c_2, \ldots, c_g). Each road has a travel time (f[u][v]). When T traverses a road, that road becomes blocked for the entire duration of T's crossing. Luka starts from inte ...

No difference between shortest paths in directed and undirected graphs (undirected graph are special cases of directed graphs) Graph storage: dense graphs (adjacency matrix) && sparse graphs (adjacency list) I. Single-Source Shortest Path 1. All edge weights are positive - Dijkstra's Algorithm Handling multiple edges and self-loops ...

Given a directed graph with nodes labeled 0 through n-1, where edge are colored either red or blue and may include self-loops and parallel edges. Each [i, j] pair in red_edges represents a red directed edge from node i to node j. Similarly, each [i, j] pair in blue_edges represents a blue directed edge from node i to node j. Compute an array re ...

The Floyd-Warshall algorithm solves the all-pairs shortest path problem in a weighted graph, handling both positive and negative edge weights (with no negative cycles). It uses dynamic programming to iteratively improve shortest path estimates between every pair of vertices. Core Principal Define dist[i][j][k] as the shortest distance from node ...

Problem Analysis Given N people with known gender (F for female, M for male), each person provides direct distance measurements to their friends. The distance between any two people is the minimum possible distance through any path of known relationships. For each person i, define their "opposite-gender distance" as the maximum value ...