{"id":"aa87634d-f73c-4613-8a84-604cc76f0deb","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path","description":"1. You are given a graph, a src vertex and a destination vertex.\r\n2. You are give a number named \"criteria\" and a number \"k\".\r\n3. You are required to find and print the values of \r\n3.1 Smallest path and it's weight separated by an \"@\"\r\n3.2 Largest path and it's weight separated by an \"@\"\r\n3.3 Just Larger path (than criteria in terms of weight) and it's weight separated by an \"@\"\r\n3.4 Just smaller path (than criteria in terms of weight) and it's weight separated by an \"@\"\r\n3.5 Kth largest path and it's weight separated by an \"@\"\r\n","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n\nclass Edge {\npublic:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt) {\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n\nstruct myComp {\n bool operator()(\n pair<int, string>& a,\n pair<int, string>& b)\n {\n return a.first > b.first;\n }\n};\nstring spath;\nint spathwt = INT_MAX;\nstring lpath;\nint lpathwt = INT_MIN;\nstring cpath;\nint cpathwt = INT_MAX;\nstring fpath;\nint fpathwt = INT_MIN;\n\npriority_queue<pair<int, string>, vector<pair<int, string>>, myComp> pq;\n\nvoid multisolver(vector<Edge> graph[], int src, int dest, vector<bool> visited, int criteria, int k, string psf, int wsf) {\n //write your code here\n}\n\nint main() {\n\n int vtces;\n cin >> vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin >> edges;\n for (int i = 0; i < edges; i++) {\n int v1 ;\n int v2 ;\n int wt ;\n cin >> v1 >> v2 >> wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin >> src;\n int dest;\n cin >> dest;\n\n int criteria;\n cin >> criteria;\n int k;\n cin >> k;\n\n vector<bool> visited(vtces, false);\n multisolver(graph, src, dest, visited, criteria, k, src + \"0\", 0);\n\n cout << \"Smallest Path = \" << spath << \"@\" << spathwt << endl;\n cout << \"Largest Path = \" << lpath << \"@\" << lpathwt << endl;\n cout << \"Just Larger Path than \" << criteria << \" = \" << cpath << \"@\" << cpathwt << endl;\n cout << \"Just Smaller Path than \" << criteria << \" = \" << fpath << \"@\" << fpathwt << endl;\n cout << k << \"th largest path = \" << pq.top().second << \"@\" << pq.top().first << endl;\n\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n static class Pair implements Comparable<Pair> {\r\n int wsf;\r\n String psf;\r\n\r\n Pair(int wsf, String psf){\r\n this.wsf = wsf;\r\n this.psf = psf;\r\n }\r\n\r\n public int compareTo(Pair o){\r\n return this.wsf - o.wsf;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n int criteria = Integer.parseInt(br.readLine());\r\n int k = Integer.parseInt(br.readLine());\r\n\r\n boolean[] visited = new boolean[vtces];\r\n multisolver(graph, src, dest, visited, criteria, k, src + \"\", 0);\r\n \r\n System.out.println(\"Smallest Path = \" + spath + \"@\" + spathwt);\r\n System.out.println(\"Largest Path = \" + lpath + \"@\" + lpathwt);\r\n System.out.println(\"Just Larger Path than \" + criteria + \" = \" + cpath + \"@\" + cpathwt);\r\n System.out.println(\"Just Smaller Path than \" + criteria + \" = \" + fpath + \"@\" + fpathwt);\r\n System.out.println(k + \"th largest path = \" + pq.peek().psf + \"@\" + pq.peek().wsf);\r\n }\r\n\r\n\r\n\r\n static String spath;\r\n static Integer spathwt = Integer.MAX_VALUE;\r\n static String lpath;\r\n static Integer lpathwt = Integer.MIN_VALUE;\r\n static String cpath;\r\n static Integer cpathwt = Integer.MAX_VALUE;\r\n static String fpath;\r\n static Integer fpathwt = Integer.MIN_VALUE;\r\n static PriorityQueue<Pair> pq = new PriorityQueue<>();\r\n public static void multisolver(ArrayList<Edge>[] graph, int src, int dest, boolean[] visited, int criteria, int k, String psf, int wsf) {\r\n \r\n }\r\n}"},"python":{"code":"import math\nimport heapq\nspath = \"\"\nspathwt = math.inf\nlpath=\"\"\nlpathwt = -math.inf\ncpath=\"\"\ncpathwt = math.inf\nfpath=\"\"\nfpathwt = -math.inf\nh = []\nclass Edge:\n \n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\n \n \ndef multisolver(graph, src, dest, visited, criteria, k, psf , wsf):\n #write your code here\n\ndef main():\n \n \n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n values = input().split(\" \")\n e1 = Edge(int(values[0]) , int(values[1]) , int(values[2]))\n e2 = Edge(int(values[1]) , int(values[0]) , int(values[2]))\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src = int(input())\n dest = int(input())\n criteria = int(input())\n k = int(input())\n \n visited = [False]*vtces\n multisolver(graph, src, dest, visited, criteria, k, str(src) , 0)\n print(\"Smallest Path =\" , spath + \"@\" + str(spathwt))\n print(\"Largest Path =\" , lpath + \"@\" + str(lpathwt))\n print(\"Just Larger Path than\" , criteria , \"=\" , cpath + \"@\" + str(cpathwt))\n print(\"Just Smaller Path than\" , criteria , \"=\" , fpath + \"@\" + str(fpathwt))\n \n \n largests = heapq.nlargest(k, h)\n \n li = largests[len(largests)-1]\n print(str(k)+\"th largest path = \"+str(li[1])+\"@\"+str(li[0]));\n \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n9\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8\r\n2 5 5\r\n0\r\n6\r\n30\r\n4","sampleOutput":"Smallest Path = 01256@28\r\nLargest Path = 032546@66\r\nJust Larger Path than 30 = 012546@36\r\nJust Smaller Path than 30 = 01256@28\r\n4th largest path = 03456@48","questionVideo":"https://www.youtube.com/embed/PSy0yJQx050?start=0&end=57","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"ee15dd59-41c8-401c-a3cc-57101f47e54c","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path","slug":"multisolver-smallest-longest-ceil-floor-kthlargest-path","type":1}],"next":{"id":"66628ba5-69be-4651-aac0-07a6a5ef5793","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kth Largest Path","type":3,"slug":"multisolver-smallest-longest-ceil-floor-kth-largest-path"},"prev":{"id":"4cc53964-8fd2-4935-b56c-65f4cac3ee0a","name":"Print All Path","type":3,"slug":"print-all-path"}}}

Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path

1. You are given a graph, a src vertex and a destination vertex. 2. You are give a number named "criteria" and a number "k". 3. You are required to find and print the values of 3.1 Smallest path and it's weight separated by an "@" 3.2 Largest path and it's weight separated by an "@" 3.3 Just Larger path (than criteria in terms of weight) and it's weight separated by an "@" 3.4 Just smaller path (than criteria in terms of weight) and it's weight separated by an "@" 3.5 Kth largest path and it's weight separated by an "@"

{"id":"aa87634d-f73c-4613-8a84-604cc76f0deb","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path","description":"1. You are given a graph, a src vertex and a destination vertex.\r\n2. You are give a number named \"criteria\" and a number \"k\".\r\n3. You are required to find and print the values of \r\n3.1 Smallest path and it's weight separated by an \"@\"\r\n3.2 Largest path and it's weight separated by an \"@\"\r\n3.3 Just Larger path (than criteria in terms of weight) and it's weight separated by an \"@\"\r\n3.4 Just smaller path (than criteria in terms of weight) and it's weight separated by an \"@\"\r\n3.5 Kth largest path and it's weight separated by an \"@\"\r\n","inputFormat":"Input has been managed for you","outputFormat":"Check sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n\nclass Edge {\npublic:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt) {\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n\nstruct myComp {\n bool operator()(\n pair<int, string>& a,\n pair<int, string>& b)\n {\n return a.first > b.first;\n }\n};\nstring spath;\nint spathwt = INT_MAX;\nstring lpath;\nint lpathwt = INT_MIN;\nstring cpath;\nint cpathwt = INT_MAX;\nstring fpath;\nint fpathwt = INT_MIN;\n\npriority_queue<pair<int, string>, vector<pair<int, string>>, myComp> pq;\n\nvoid multisolver(vector<Edge> graph[], int src, int dest, vector<bool> visited, int criteria, int k, string psf, int wsf) {\n //write your code here\n}\n\nint main() {\n\n int vtces;\n cin >> vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin >> edges;\n for (int i = 0; i < edges; i++) {\n int v1 ;\n int v2 ;\n int wt ;\n cin >> v1 >> v2 >> wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin >> src;\n int dest;\n cin >> dest;\n\n int criteria;\n cin >> criteria;\n int k;\n cin >> k;\n\n vector<bool> visited(vtces, false);\n multisolver(graph, src, dest, visited, criteria, k, src + \"0\", 0);\n\n cout << \"Smallest Path = \" << spath << \"@\" << spathwt << endl;\n cout << \"Largest Path = \" << lpath << \"@\" << lpathwt << endl;\n cout << \"Just Larger Path than \" << criteria << \" = \" << cpath << \"@\" << cpathwt << endl;\n cout << \"Just Smaller Path than \" << criteria << \" = \" << fpath << \"@\" << fpathwt << endl;\n cout << k << \"th largest path = \" << pq.top().second << \"@\" << pq.top().first << endl;\n\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n int wt;\r\n\r\n Edge(int src, int nbr, int wt) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\r\n }\r\n }\r\n\r\n static class Pair implements Comparable<Pair> {\r\n int wsf;\r\n String psf;\r\n\r\n Pair(int wsf, String psf){\r\n this.wsf = wsf;\r\n this.psf = psf;\r\n }\r\n\r\n public int compareTo(Pair o){\r\n return this.wsf - o.wsf;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n int criteria = Integer.parseInt(br.readLine());\r\n int k = Integer.parseInt(br.readLine());\r\n\r\n boolean[] visited = new boolean[vtces];\r\n multisolver(graph, src, dest, visited, criteria, k, src + \"\", 0);\r\n \r\n System.out.println(\"Smallest Path = \" + spath + \"@\" + spathwt);\r\n System.out.println(\"Largest Path = \" + lpath + \"@\" + lpathwt);\r\n System.out.println(\"Just Larger Path than \" + criteria + \" = \" + cpath + \"@\" + cpathwt);\r\n System.out.println(\"Just Smaller Path than \" + criteria + \" = \" + fpath + \"@\" + fpathwt);\r\n System.out.println(k + \"th largest path = \" + pq.peek().psf + \"@\" + pq.peek().wsf);\r\n }\r\n\r\n\r\n\r\n static String spath;\r\n static Integer spathwt = Integer.MAX_VALUE;\r\n static String lpath;\r\n static Integer lpathwt = Integer.MIN_VALUE;\r\n static String cpath;\r\n static Integer cpathwt = Integer.MAX_VALUE;\r\n static String fpath;\r\n static Integer fpathwt = Integer.MIN_VALUE;\r\n static PriorityQueue<Pair> pq = new PriorityQueue<>();\r\n public static void multisolver(ArrayList<Edge>[] graph, int src, int dest, boolean[] visited, int criteria, int k, String psf, int wsf) {\r\n \r\n }\r\n}"},"python":{"code":"import math\nimport heapq\nspath = \"\"\nspathwt = math.inf\nlpath=\"\"\nlpathwt = -math.inf\ncpath=\"\"\ncpathwt = math.inf\nfpath=\"\"\nfpathwt = -math.inf\nh = []\nclass Edge:\n \n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\n \n \ndef multisolver(graph, src, dest, visited, criteria, k, psf , wsf):\n #write your code here\n\ndef main():\n \n \n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n values = input().split(\" \")\n e1 = Edge(int(values[0]) , int(values[1]) , int(values[2]))\n e2 = Edge(int(values[1]) , int(values[0]) , int(values[2]))\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src = int(input())\n dest = int(input())\n criteria = int(input())\n k = int(input())\n \n visited = [False]*vtces\n multisolver(graph, src, dest, visited, criteria, k, str(src) , 0)\n print(\"Smallest Path =\" , spath + \"@\" + str(spathwt))\n print(\"Largest Path =\" , lpath + \"@\" + str(lpathwt))\n print(\"Just Larger Path than\" , criteria , \"=\" , cpath + \"@\" + str(cpathwt))\n print(\"Just Smaller Path than\" , criteria , \"=\" , fpath + \"@\" + str(fpathwt))\n \n \n largests = heapq.nlargest(k, h)\n \n li = largests[len(largests)-1]\n print(str(k)+\"th largest path = \"+str(li[1])+\"@\"+str(li[0]));\n \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n9\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8\r\n2 5 5\r\n0\r\n6\r\n30\r\n4","sampleOutput":"Smallest Path = 01256@28\r\nLargest Path = 032546@66\r\nJust Larger Path than 30 = 012546@36\r\nJust Smaller Path than 30 = 01256@28\r\n4th largest path = 03456@48","questionVideo":"https://www.youtube.com/embed/PSy0yJQx050?start=0&end=57","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"ee15dd59-41c8-401c-a3cc-57101f47e54c","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path","slug":"multisolver-smallest-longest-ceil-floor-kthlargest-path","type":1}],"next":{"id":"66628ba5-69be-4651-aac0-07a6a5ef5793","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kth Largest Path","type":3,"slug":"multisolver-smallest-longest-ceil-floor-kth-largest-path"},"prev":{"id":"4cc53964-8fd2-4935-b56c-65f4cac3ee0a","name":"Print All Path","type":3,"slug":"print-all-path"}}}
plane

Editor

Loading...

Multisolver - Smallest, Longest, Ceil, Floor, Kthlargest Path

easy

1. You are given a graph, a src vertex and a destination vertex. 2. You are give a number named "criteria" and a number "k". 3. You are required to find and print the values of 3.1 Smallest path and it's weight separated by an "@" 3.2 Largest path and it's weight separated by an "@" 3.3 Just Larger path (than criteria in terms of weight) and it's weight separated by an "@" 3.4 Just smaller path (than criteria in terms of weight) and it's weight separated by an "@" 3.5 Kth largest path and it's weight separated by an "@"

Constraints

None

Format

Input

Input has been managed for you

Output

Check sample output

Example

Sample Input

7 9 0 1 10 1 2 10 2 3 10 0 3 40 3 4 2 4 5 3 5 6 3 4 6 8 2 5 5 0 6 30 4

Sample Output

Smallest Path = 01256@28 Largest Path = 032546@66 Just Larger Path than 30 = 012546@36 Just Smaller Path than 30 = 01256@28 4th largest path = 03456@48

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode