Scribd Logo
Upload

Welcome to Scribd!

  • 24 views

    Newton School: Newton's Grand Contest 2021 - Homecoming (Public Contest: August 2021)

    Uploaded by

    Everything Anything Yash

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Newton School: Newton's Grand Contest 2021 - Homecoming (Public Contest: August 2021)

    Uploaded by

    Everything Anything Yash
    24 views2 pages

    Original Title

    q4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    24 views2 pages

    Newton School: Newton's Grand Contest 2021 - Homecoming (Public Contest: August 2021)

    Uploaded by

    Everything Anything Yash

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    8/27/2021 Newton School

    Newton School PL

    back
    Save and Run Hidden Test
    Newton's Grand Contest 2021 - Homecoming (Public Contest: August 2021) by Pranav 01:42:45
    Run Cases
    Lad

    Homecoming (Public Contest: August 2021)

    standard input/output: 2s/512000 kB

    There are n cities in the universe and our beloved Spider-Man is in city 1. He doesn't like to travel by vehicles, so he shot webs forming edges between some pairs of cities.
    Eventually, there were m edges and each had some cost associated with it.

    Spider-Man now defines the cost of a path p from cities p1 to pk as w1 + 2w2 + 3w3 . . . + (k-1)*wk-1, where wi is the cost of an edge from pi to pi+1.
    Thus, the minimum distance between cities i and j is the smallest cost of a path starting from i and ending at j.

    Find the minimum distance from city 1 to all the cities i (1 ≤ i ≤ n). If there exists no way to go from city 1 to city i, print -1.

    Note:
    All the edges are bidirectional. There may be multiple edges and self-loops in the input.

    Input
    The first line contains two space separated integers n and m - the number of nodes and edges respectively.

    The next m lines contain three-space separated integers x, y, w - representing an edge between x and y with cost w.

    Constraints:

    1 ≤ n ≤ 3000

    0 ≤ m ≤ 10000

    1 ≤ x, y ≤ n

    1 ≤ w ≤ 109

    Output
    Output n lines. In the ith line, output the minimum distance from city 1 to the ith city. If there exists no such path, output -1.

    Example
    Sample Input
    6 5
    2 4 3
    2 3 4
    2 1 2
    2 5 6
    1 5 2
     
    Sample Output
    0
    2

    Code Reset C++ (GCC 9.2.0) Custom Input


    1
    1 #include <bits/stdc++.h> // header file includes every Standard library
    2 using namespace std;
    3  
    4 int main() {
    5  
    6     // Your code here
    7     return 0;
    8 }
    9  

    STDOUT STDERR COMPILE OUTPUT MESSAGE


    1

    Test Cases Previous Submissions

    Test case 0 Hidden test case Status Test Cases Passed

    Test case 1

    Test case 2

    Test caseHelp
    3

    Test case 4
    https://my.newtonschool.co/playground/code/ixl3ewis2jr5/ 1/2
    8/27/2021 Newton School
    Test case 4

    Test case 5

    Test case 6

    Test case 7

    Test case 8

    Test case 9

    © 2021 Incanus Technologies Pvt Ltd


    For any queries, you can reach us at Follow us on
    All rights reserved. (Terms) support@newtonschool.co

    https://my.newtonschool.co/playground/code/ixl3ewis2jr5/ 2/2

    You might also like