{"id":"057467be-95c9-499e-b93b-89f56f5b87f0","name":"Shortest Path In Weights","description":"1. You are given a graph and a source vertex. The vertices represent cities and the edges represent \r\n distance in kms.\r\n2. You are required to find the shortest path to each city (in terms of kms) from the source city along \r\n with the total distance on path from source to destinations.\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n int wt = 0;\n\n Edge(int src, int nbr, int wt)\n {\n this->src = src; \n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n \n \n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w; \n \n graph[u].push_back(Edge(u, v, w));\n graph[v].push_back(Edge(v, u, w));\n\n } \n int src; \n cin >> src; \n \n //write your code here \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 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 // write your code here\r\n \r\n }\r\n}"},"python":{"code":"import threading \n\n\n\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt=wt\n\n\n\ndef main():\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 lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n wt=int(lines[2])\n e1 = Edge(v1 ,v2 ,wt)\n e2 = Edge(v2 ,v1 ,wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src = int(input())\n \n #write your code here\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","sampleOutput":"0 via 0 @ 0\r\n1 via 01 @ 10\r\n2 via 012 @ 20\r\n5 via 0125 @ 25\r\n4 via 01254 @ 28\r\n6 via 01256 @ 28\r\n3 via 012543 @ 30","questionVideo":"https://www.youtube.com/embed/sD0lLYlGCJE?end=104","hints":[],"associated":[{"id":"14ee1e83-4aa7-4449-b03c-917159f53672","name":"what is the time complexity of this \"Shortest Path in Weights\" problem?","slug":"what-is-the-time-complexity-of-this-shortest-path-in-weights-problem-66wk0","type":4},{"id":"85b41713-20f6-44e7-b9ad-d693fb4067c4","name":"Which kind of approach this \"Shortest Path in Weights\" algorithm follows?","slug":"which-kind-of-approach-this-shortest-path-in-weights-algorithm-follows","type":4},{"id":"b97befa3-5a71-4ca4-8461-24a1e47c1d43","name":"What is the name of this , \"Shortest Path in Weights\" algorithm?","slug":"what-is-the-name-of-this-shortest-path-in-weights-algorithm","type":4}],"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":"0632ae01-22d2-4845-b8e3-36a2590f0e42","name":"Shortest Path In Weights","slug":"shortest-path-in-weights","type":1}],"next":{"id":"920b9140-9643-4c4f-889e-6ad352029d24","name":"Shortest Path in weights","type":3,"slug":"shortest-path-in-weights"},"prev":{"id":"51dac32b-6457-4a0d-b76a-0709e27b857f","name":"Spread of Infection","type":3,"slug":"spread-of-infection"}}}

Shortest Path In Weights

1. You are given a graph and a source vertex. The vertices represent cities and the edges represent distance in kms. 2. You are required to find the shortest path to each city (in terms of kms) from the source city along with the total distance on path from source to destinations. Note -> For output, check the sample output and question video.

{"id":"057467be-95c9-499e-b93b-89f56f5b87f0","name":"Shortest Path In Weights","description":"1. You are given a graph and a source vertex. The vertices represent cities and the edges represent \r\n distance in kms.\r\n2. You are required to find the shortest path to each city (in terms of kms) from the source city along \r\n with the total distance on path from source to destinations.\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n int wt = 0;\n\n Edge(int src, int nbr, int wt)\n {\n this->src = src; \n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n \n \n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w; \n \n graph[u].push_back(Edge(u, v, w));\n graph[v].push_back(Edge(v, u, w));\n\n } \n int src; \n cin >> src; \n \n //write your code here \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 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 // write your code here\r\n \r\n }\r\n}"},"python":{"code":"import threading \n\n\n\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt=wt\n\n\n\ndef main():\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 lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n wt=int(lines[2])\n e1 = Edge(v1 ,v2 ,wt)\n e2 = Edge(v2 ,v1 ,wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src = int(input())\n \n #write your code here\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","sampleOutput":"0 via 0 @ 0\r\n1 via 01 @ 10\r\n2 via 012 @ 20\r\n5 via 0125 @ 25\r\n4 via 01254 @ 28\r\n6 via 01256 @ 28\r\n3 via 012543 @ 30","questionVideo":"https://www.youtube.com/embed/sD0lLYlGCJE?end=104","hints":[],"associated":[{"id":"14ee1e83-4aa7-4449-b03c-917159f53672","name":"what is the time complexity of this \"Shortest Path in Weights\" problem?","slug":"what-is-the-time-complexity-of-this-shortest-path-in-weights-problem-66wk0","type":4},{"id":"85b41713-20f6-44e7-b9ad-d693fb4067c4","name":"Which kind of approach this \"Shortest Path in Weights\" algorithm follows?","slug":"which-kind-of-approach-this-shortest-path-in-weights-algorithm-follows","type":4},{"id":"b97befa3-5a71-4ca4-8461-24a1e47c1d43","name":"What is the name of this , \"Shortest Path in Weights\" algorithm?","slug":"what-is-the-name-of-this-shortest-path-in-weights-algorithm","type":4}],"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":"0632ae01-22d2-4845-b8e3-36a2590f0e42","name":"Shortest Path In Weights","slug":"shortest-path-in-weights","type":1}],"next":{"id":"920b9140-9643-4c4f-889e-6ad352029d24","name":"Shortest Path in weights","type":3,"slug":"shortest-path-in-weights"},"prev":{"id":"51dac32b-6457-4a0d-b76a-0709e27b857f","name":"Spread of Infection","type":3,"slug":"spread-of-infection"}}}
plane

Editor

Loading...

Shortest Path In Weights

easy

1. You are given a graph and a source vertex. The vertices represent cities and the edges represent distance in kms. 2. You are required to find the shortest path to each city (in terms of kms) from the source city along with the total distance on path from source to destinations. Note -> For output, check the sample output and question video.

Constraints

None

Format

Input

Input has been managed for you

Output

Check the 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

Sample Output

0 via 0 @ 0 1 via 01 @ 10 2 via 012 @ 20 5 via 0125 @ 25 4 via 01254 @ 28 6 via 01256 @ 28 3 via 012543 @ 30

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode