23:I[344796,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2sk2f47durg8o.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/1wo5i8je1ygp5.js","/_next/static/chunks/1h4l04ysuholp.js","/_next/static/chunks/2qcnia-og0qh0.js","/_next/static/chunks/40webkzfr6rcp.js"],"default"] 2a:I[27201,["/_next/static/chunks/083cs_iw_ie0y.js","/_next/static/chunks/2sk2f47durg8o.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/1wo5i8je1ygp5.js","/_next/static/chunks/1h4l04ysuholp.js","/_next/static/chunks/2qcnia-og0qh0.js"],"IconMark"] 24:Tf5b,

Roads on Fastest Delivery Routes

Uber operates a road network connecting n cities, numbered from 0 to n - 1. The network is an undirected weighted graph: every road connects two cities and has an associated travel time.

For planning premium deliveries, Uber wants to identify all roads that belong to at least one fastest route from the main distribution center (city 0) to the destination hub (city n - 1). A fastest route is any route whose total travel time is the minimum possible over all routes from city 0 to city n - 1.

Given the road network, determine for every road whether it appears on at least one fastest route from city 0 to city n - 1.

Input

The first line contains two integers n and m — the number of cities and the number of roads.
Each of the next m lines contains three integers u v w, describing a road between cities u and v with travel time w. Roads are undirected.

Output

Print m space-separated tokens on a single line. The i-th token (0-indexed, in the same order the roads were given in the input) is true if road i lies on at least one fastest route from city 0 to city n - 1, and false otherwise.

Constraints

2 <= n <= 3000
1 <= m <= 3000
0 <= u, v <= n - 1
1 <= w <= 10^6
The road network is connected, so city n - 1 is always reachable from city 0.
The graph may contain cycles. Multiple roads may connect the same pair of cities (parallel roads); each such road is judged independently by its own index.

Notes

Cities are 0-indexed. The source is always city 0 and the destination is always city n - 1.
A road counts as true if it is used by any fastest route, not only by one particular route; several fastest routes of equal minimum total travel time may exist and their roads are all reported true.
The total travel time of a route can exceed 2^31, so 64-bit arithmetic is required for accumulating travel times.
Output the answers strictly in input order.

Example 1

Input:

Output:

true true true false true true true false

The minimum travel time from city 0 to city 5 is 5. Several fastest routes achieve it, for example 0 -> 1 -> 5 (4 + 1), 0 -> 2 -> 3 -> 1 -> 5 (1 + 1 + 2 + 1) and 0 -> 2 -> 3 -> 5 (1 + 1 + 3). Every road that appears on some such route is marked true; roads [1,4,3] (index 3) and [4,5,2] (index 7) appear on no fastest route.

Example 2

Input:

Output:

true false false true

The minimum travel time from city 0 to city 3 is 3, achieved only by 0 -> 2 -> 3 (1 + 2). Road [2,0,1] (index 0) and road [3,2,2] (index 3) lie on it, so they are true; the direct road [0,3,4] (index 2, travel time 4) and road [0,1,1] (index 1, a dead end for this trip) are false.

25:T688,#include using namespace std; typedef long long ll; const ll INF = (ll)4e18; static void dijkstra(int n, const vector>>& adj, int src, vector& dist) { dist.assign(n, INF); dist[src] = 0; priority_queue, vector>, greater>> pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (auto& e : adj[u]) { int v = e.first; ll w = e.second; if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin >> n >> m)) return 0; vector> edges(m); vector>> adj(n); for (int i = 0; i < m; i++) { int u, v; ll w; cin >> u >> v >> w; edges[i] = {(ll)u, (ll)v, w}; adj[u].push_back({v, (int)w}); adj[v].push_back({u, (int)w}); } vector d0, dt; dijkstra(n, adj, 0, d0); dijkstra(n, adj, n - 1, dt); ll D = d0[n - 1]; string out; out.reserve(m * 6); for (int i = 0; i < m; i++) { int u = (int)edges[i][0], v = (int)edges[i][1]; ll w = edges[i][2]; bool on = false; if (D < INF) { if (d0[u] < INF && dt[v] < INF && d0[u] + w + dt[v] == D) on = true; if (d0[v] < INF && dt[u] < INF && d0[v] + w + dt[u] == D) on = true; } if (i) out += ' '; out += on ? "true" : "false"; } out += '\n'; cout << out; return 0; } 26:T4c3,import sys import heapq def dijkstra(n, adj, src): INF = float("inf") dist = [INF] * n dist[src] = 0 pq = [(0, src)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in adj[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(pq, (nd, v)) return dist def main(): data = sys.stdin.buffer.read().split() if not data: return idx = 0 n = int(data[idx]); idx += 1 m = int(data[idx]); idx += 1 edges = [] adj = [[] for _ in range(n)] for _ in range(m): u = int(data[idx]); v = int(data[idx + 1]); w = int(data[idx + 2]); idx += 3 edges.append((u, v, w)) adj[u].append((v, w)) adj[v].append((u, w)) d0 = dijkstra(n, adj, 0) dt = dijkstra(n, adj, n - 1) D = d0[n - 1] out = [] INF = float("inf") if D == INF: out = ["false"] * m else: for (u, v, w) in edges: on = (d0[u] + w + dt[v] == D) or (d0[v] + w + dt[u] == D) out.append("true" if on else "false") sys.stdout.write(" ".join(out) + "\n") if __name__ == "__main__": main() 27:T58f,import java.util.*; import java.io.*; public class Main { // roads[i] = {u, v, w} (undirected). Return a boolean[], one per road, // true if road i lies on at least one shortest path from 0 to n-1. static boolean[] findFastestRouteEdges(int n, int[][] roads) { // Write your code here return new boolean[roads.length]; } public static void main(String[] args) throws IOException { DataInputStream in = new DataInputStream(new BufferedInputStream(System.in)); int n = nextInt(in), m = nextInt(in); int[][] roads = new int[m][3]; for (int i = 0; i < m; i++) { roads[i][0] = nextInt(in); roads[i][1] = nextInt(in); roads[i][2] = nextInt(in); } boolean[] ans = findFastestRouteEdges(n, roads); StringBuilder sb = new StringBuilder(); for (int i = 0; i < ans.length; i++) { if (i > 0) sb.append(' '); sb.append(ans[i] ? "true" : "false"); } System.out.println(sb.toString()); } private static int nextInt(DataInputStream in) throws IOException { int ret = 0, b; boolean neg = false; do { b = in.read(); } while (b != '-' && (b < '0' || b > '9')); if (b == '-') { neg = true; b = in.read(); } while (b >= '0' && b <= '9') { ret = ret * 10 + (b - '0'); b = in.read(); } return neg ? -ret : ret; } } 28:Tb68,# Roads on Fastest Delivery Routes Uber operates a road network connecting `n` cities, numbered from `0` to `n - 1`. The network is an **undirected weighted graph**: every road connects two cities and has an associated travel time. For planning premium deliveries, Uber wants to identify all roads that belong to **at least one fastest route** from the main distribution center (city `0`) to the destination hub (city `n - 1`). A fastest route is any route whose total travel time is the minimum possible over all routes from city `0` to city `n - 1`. Given the road network, determine for **every** road whether it appears on at least one fastest route from city `0` to city `n - 1`. ## Input - The first line contains two integers `n` and `m` — the number of cities and the number of roads. - Each of the next `m` lines contains three integers `u v w`, describing a road between cities `u` and `v` with travel time `w`. Roads are undirected. ## Output Print `m` space-separated tokens on a single line. The `i`-th token (0-indexed, in the same order the roads were given in the input) is `true` if road `i` lies on at least one fastest route from city `0` to city `n - 1`, and `false` otherwise. ## Constraints - `2 <= n <= 3000` - `1 <= m <= 3000` - `0 <= u, v <= n - 1` - `1 <= w <= 10^6` - The road network is connected, so city `n - 1` is always reachable from city `0`. - The graph may contain cycles. Multiple roads may connect the same pair of cities (parallel roads); each such road is judged independently by its own index. ## Notes - Cities are 0-indexed. The source is always city `0` and the destination is always city `n - 1`. - A road counts as `true` if it is used by **any** fastest route, not only by one particular route; several fastest routes of equal minimum total travel time may exist and their roads are all reported `true`. - The total travel time of a route can exceed 2^31, so 64-bit arithmetic is required for accumulating travel times. - Output the answers strictly in input order. ## Example 1 Input: ``` 6 8 0 1 4 0 2 1 1 3 2 1 4 3 1 5 1 2 3 1 3 5 3 4 5 2 ``` Output: ``` true true true false true true true false ``` The minimum travel time from city `0` to city `5` is `5`. Several fastest routes achieve it, for example `0 -> 1 -> 5` (`4 + 1`), `0 -> 2 -> 3 -> 1 -> 5` (`1 + 1 + 2 + 1`) and `0 -> 2 -> 3 -> 5` (`1 + 1 + 3`). Every road that appears on some such route is marked `true`; roads `[1,4,3]` (index 3) and `[4,5,2]` (index 7) appear on no fastest route. ## Example 2 Input: ``` 4 4 2 0 1 0 1 1 0 3 4 3 2 2 ``` Output: ``` true false false true ``` The minimum travel time from city `0` to city `3` is `3`, achieved only by `0 -> 2 -> 3` (`1 + 2`). Road `[2,0,1]` (index 0) and road `[3,2,2]` (index 3) lie on it, so they are `true`; the direct road `[0,3,4]` (index 2, travel time `4`) and road `[0,1,1]` (index 1, a dead end for this trip) are `false`.29:Tb8c,# Editorial: Roads on Fastest Delivery Routes ## Overview We are given an undirected weighted connected graph and must decide, for every edge, whether it lies on at least one shortest path between a fixed source `0` and a fixed destination `n - 1`. The number of such qualifying edges can be large because many equal-cost shortest routes may coexist, so we need a criterion that tests each edge independently rather than enumerating routes. ## Key Insight An edge `(u, v)` with weight `w` lies on some shortest `0 -> n - 1` path if and only if it can be "sandwiched" between a shortest path from `0` to one endpoint and a shortest path from the other endpoint to `n - 1`. Concretely, let `dist0[x]` be the shortest distance from `0` to `x`, and `distT[x]` the shortest distance from `x` to `n - 1`. Let `D = dist0[n - 1]` be the overall shortest distance. The edge qualifies exactly when using it in one of its two orientations produces a full route of total length `D`. ## Approach Run Dijkstra twice: once from the source `0` to obtain `dist0`, and once from the destination `n - 1` to obtain `distT` (the graph is undirected, so a single Dijkstra from `n - 1` gives the distance from every node to `n - 1`). Compute `D = dist0[n - 1]`. Then for each edge `(u, v, w)`, mark it `true` if `dist0[u] + w + distT[v] == D` or `dist0[v] + w + distT[u] == D`, and `false` otherwise. Emit the results in input order. ## Why This Works If an edge is on some shortest path, that path reaches one endpoint optimally from the source, crosses the edge, and continues optimally to the destination — which is precisely one of the two equality conditions summing to `D`. Conversely, whenever an equality holds, concatenating a shortest `0`-to-endpoint path, the edge, and a shortest endpoint-to-`n - 1` path yields a valid route of length exactly `D`, i.e. a genuine shortest path through that edge. Because both directions of the undirected edge are tested, orientation never causes a miss. Handling each edge by index also makes parallel roads and self-loops fall out correctly. ## Complexity Two Dijkstra runs with a binary heap cost `O((n + m) log n)` time and `O(n + m)` space; the final per-edge scan is `O(m)`. ## Common Pitfalls - Testing only one orientation (`dist0[u] + w + distT[v]`) misses edges whose input orientation is reversed relative to the route — always test both. - Using distances only from the source (edge is "tight" if `dist0[u] + w == dist0[v]`) marks edges that lie on a shortest path to some intermediate node but never reach the destination on a shortest route. - Marking edges of a single recovered shortest path only; the problem asks for the union over all shortest paths, so many equal-cost alternatives must be counted. - Accumulated travel times can exceed 2^31; use 64-bit integers for the distances. - Reporting answers out of input order, or collapsing parallel roads instead of judging each road index separately.1c:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"Roads on Fastest Delivery Routes\",\"description\":\"Roads on Fastest Delivery Routes Uber operates a road network connecting n cities, numbered from 0 to n - 1 . The network is an undirected weighted graph : every road connects two cities and has an associated travel time. For planning premium deliveries, Uber wants to identify all roads that belong to at least one fastest route from the main distribution center (city 0 ) to the destination hub (city n - 1 ). A fastest route is any route whose total travel time is the minimum possible over all ro\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"Uber_23july\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://oahelper.in\"},\"url\":\"https://oahelper.in/problems/NTIyOHww/roads-on-fastest-delivery-routes\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Roads on Fastest Delivery Routes\",\"item\":\"https://oahelper.in/problems/NTIyOHww/roads-on-fastest-delivery-routes\"}]}"}}],["$","section",null,{"className":"sr-only","aria-hidden":"true","children":[["$","p",null,{"children":["Company: ","Uber_23july"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"Roads on Fastest Delivery Routes Uber operates a road network connecting n cities, numbered from 0 to n - 1 . The network is an undirected weighted graph : every road connects two cities and has an associated travel time. For planning premium deliveries, Uber wants to identify all roads that belong to at least one fastest route from the main distribution center (city 0 ) to the destination hub (city n - 1 ). A fastest route is any route whose total travel time is the minimum possible over all routes from city 0 to city n - 1 . Given the road network, determine for every road whether it appears on at least one fastest route from city 0 to city n - 1 . Input The first line contains two integers n and m — the number of cities and the number of roads. Each of the next m lines contains three integers u v w , describing a road between cities u and v with travel time w . Roads are undirected. Output Print m space-separated tokens on a single line. The i -th token (0-indexed, in the same order"}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$Lb",null,{"href":"/company-questions/uber23july","children":["More ","Uber_23july"," OA questions"]}],["$","$Lb",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],["$","$L23",null,{"id":"NTIyOHww","initialQuestion":{"id":"NTIyOHww","title":"Roads on Fastest Delivery Routes","google_doc_link":null,"problem_statement":"$24","solution_cpp":"$25","solution_python":"$26","solution_java":null,"pregiven_code_cpp":"#include \nusing namespace std;\n\n// roads[i] = {u, v, w} (undirected). Return a vector, one per road,\n// true if road i lies on at least one shortest path from 0 to n-1.\nvector findFastestRouteEdges(int n, vector>& roads) {\n // Write your code here\n return vector(roads.size(), false);\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n int n, m;\n if (!(cin >> n >> m)) return 0;\n vector> roads(m, vector(3));\n for (int i = 0; i < m; i++) cin >> roads[i][0] >> roads[i][1] >> roads[i][2];\n vector ans = findFastestRouteEdges(n, roads);\n for (size_t i = 0; i < ans.size(); i++) {\n if (i) cout << ' ';\n cout << (ans[i] ? \"true\" : \"false\");\n }\n cout << '\\n';\n return 0;\n}\n","pregiven_code_python":"import sys\n\n\ndef findFastestRouteEdges(n, roads):\n # roads[i] = [u, v, w] (undirected). Return a list of bool, one per road,\n # True if road i lies on at least one shortest path from 0 to n-1.\n # Write your code here\n return [False] * len(roads)\n\n\ndef main():\n data = sys.stdin.buffer.read().split()\n if not data:\n return\n idx = 0\n n = int(data[idx]); idx += 1\n m = int(data[idx]); idx += 1\n roads = []\n for _ in range(m):\n u = int(data[idx]); v = int(data[idx + 1]); w = int(data[idx + 2]); idx += 3\n roads.append([u, v, w])\n ans = findFastestRouteEdges(n, roads)\n print(\" \".join(\"true\" if x else \"false\" for x in ans))\n\n\nif __name__ == \"__main__\":\n main()\n","pregiven_code_java":"$27","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2026-07-24T21:38:09.852699+00:00","updated_at":"2026-08-10T00:00:41.15244+00:00","solution_code":null,"solution":null,"pregiven_code":"#include \nusing namespace std;\n\n// roads[i] = {u, v, w} (undirected). Return a vector, one per road,\n// true if road i lies on at least one shortest path from 0 to n-1.\nvector findFastestRouteEdges(int n, vector>& roads) {\n // Write your code here\n return vector(roads.size(), false);\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n int n, m;\n if (!(cin >> n >> m)) return 0;\n vector> roads(m, vector(3));\n for (int i = 0; i < m; i++) cin >> roads[i][0] >> roads[i][1] >> roads[i][2];\n vector ans = findFastestRouteEdges(n, roads);\n for (size_t i = 0; i < ans.size(); i++) {\n if (i) cout << ' ';\n cout << (ans[i] ? \"true\" : \"false\");\n }\n cout << '\\n';\n return 0;\n}\n","input_test_case":"[\"6 8\\n0 1 4\\n0 2 1\\n1 3 2\\n1 4 3\\n1 5 1\\n2 3 1\\n3 5 3\\n4 5 2\\n\", \"4 4\\n2 0 1\\n0 1 1\\n0 3 4\\n3 2 2\\n\"]","output_test_case":"[\"true true true false true true true false\\n\", \"true false false true\\n\"]","lc_tags":"[\"Graph\", \"Shortest Path\", \"Heap (Priority Queue)\", \"Breadth-First Search\"]","visual_animation":null,"difficulty_score":50,"md_problem_statement":"$28","unique_company_name":"uber","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$29","hidden_test_cases_blob_count":80,"youtube_tutorial":null,"prompt_solution":null,"campus_type":"on_campus","college_name":null,"role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"Uber_23july","is_first_in_company":true,"company_ref":"MTYxM3ww","total_test_cases":15,"hidden_test_cases_count":13},"isQotdToday":false,"qotdReward":5}]] 1e:null 22:[["$","title","0",{"children":"Roads on Fastest Delivery Routes - Uber_23july OA Question | OAHelper"}],["$","meta","1",{"name":"description","content":"Roads on Fastest Delivery Routes (Uber_23july OA) - medium: Roads on Fastest Delivery Routes Uber operates a road network connecting n cities, numbered from 0 to n - 1 . The network is an undirected weighted graph : ever…"}],["$","meta","2",{"name":"author","content":"OAHelper Team"}],["$","meta","3",{"name":"keywords","content":"Uber_23july OA question, Uber_23july online assessment, Roads on Fastest Delivery Routes, medium, online assessment, coding question, OA practice, interview preparation"}],["$","meta","4",{"name":"robots","content":"index, follow"}],["$","meta","5",{"name":"googlebot","content":"index, follow, max-video-preview:-1, max-image-preview:large, max-snippet:-1"}],["$","link","6",{"rel":"canonical","href":"https://oahelper.in/problems/NTIyOHww/roads-on-fastest-delivery-routes"}],["$","meta","7",{"name":"google-site-verification","content":"MCxApq58khiH0y4KRigRUpoTS3ckefkhoCSHRIRLiXo"}],["$","meta","8",{"property":"og:title","content":"Roads on Fastest Delivery Routes - Uber_23july OA Question | OAHelper"}],["$","meta","9",{"property":"og:description","content":"Roads on Fastest Delivery Routes (Uber_23july OA) - medium: Roads on Fastest Delivery Routes Uber operates a road network connecting n cities, numbered from 0 to n - 1 . The network is an undirected weighted graph : ever…"}],["$","meta","10",{"property":"og:url","content":"https://oahelper.in/problems/NTIyOHww/roads-on-fastest-delivery-routes"}],["$","meta","11",{"property":"og:site_name","content":"OAHelper"}],["$","meta","12",{"property":"og:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","meta","13",{"property":"og:image:width","content":"256"}],["$","meta","14",{"property":"og:image:height","content":"256"}],["$","meta","15",{"property":"og:image:alt","content":"Roads on Fastest Delivery Routes - Uber_23july OA Question"}],["$","meta","16",{"property":"og:type","content":"website"}],["$","meta","17",{"name":"twitter:card","content":"summary_large_image"}],["$","meta","18",{"name":"twitter:title","content":"Roads on Fastest Delivery Routes - Uber_23july OA Question | OAHelper"}],["$","meta","19",{"name":"twitter:description","content":"Roads on Fastest Delivery Routes (Uber_23july OA) - medium: Roads on Fastest Delivery Routes Uber operates a road network connecting n cities, numbered from 0 to n - 1 . The network is an undirected weighted graph : ever…"}],["$","meta","20",{"name":"twitter:image","content":"https://oahelper.in/campus-ceo-favicon.png?v=11"}],["$","link","21",{"rel":"shortcut icon","href":"/campus-ceo-favicon.png?v=11"}],["$","link","22",{"rel":"icon","href":"/campus-ceo-favicon-128.png?v=11","sizes":"128x128","type":"image/png"}],["$","link","23",{"rel":"icon","href":"/campus-ceo-favicon.png?v=11","sizes":"256x256","type":"image/png"}],["$","link","24",{"rel":"icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"512x512","type":"image/png"}],["$","link","25",{"rel":"apple-touch-icon","href":"/campus-ceo-favicon-512.png?v=11","sizes":"180x180","type":"image/png"}],["$","$L2a","26",{}]]