oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

supplies Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

supplies.html

Problem Description

Ranald the cat wants to get some supplies from some faraway land and return back home. Since the 'faraway land' is so far away, there might or might not be direct transportation services/routes to that location from Ranald's house.

Ranald has investigated the bus routes from his house to the faraway land and has counted a total of N bus stops/interchanges labelled from 0 to N-1 and E bus routes. Each bus route costs a certain amount of money (C) and ferries people from bus stop A to bus stop B

A person (or cat) can get from one bus stop to another via buses (you don't say) but since some routes aren't bi-directional, the cost of travelling from bus stop 1 to bus stop 2 could be different from travelling from bus stop 2 to bus stop 1.

Ranald wants to know how much money would he need to spend on transportation if he decides to get the supplies and return back home. (If it costs too much, he can order it from Ebay ^^)

No 2 routes will have the same A and B.

Input

The first line of input consists of 4 integers: N, E, H and T. H represents which bus stop Ranald the cat will be starting in and T represents which bus stop the supplies Ranald wants would be located at.

Subsequently, E lines follow with 3 integers each: A, B and C. Each line describes a bus route, meaning there is a bus service that services from bus stop A to bus stop B and requires $C.

Output

Output a single integer, the amount of money Ranald would spend on transportation if he decides to go get the supplies and returns home.

If it is impossible (no route) to get the supplies and return home, output -1 instead.

Limits

0 ≤ A, B, H, T < N

0 ≤ C ≤ 10000

Subtask 1 (20%): 0 < N ≤ 5

Subtask 2 (30%): 0 < N ≤ 100

Subtask 3 (50%): 0 < N ≤ 1000

Sample Input 1

4 8 0 3
0 1 1
1 0 4
1 3 5
1 2 3
2 0 3
2 3 1
2 1 8
3 2 6

Sample Output 1

14

Explanation for Sample Output 1

It takes $5 to get from bus stop 0 to bus stop 3. It takes $9 to get from bus stop 3 to bus stop 0.

Sample Input 2

4 8 1 3
0 1 1
1 0 4
1 3 5
1 2 3
2 0 3
2 3 1
2 1 8
3 2 6

Sample Output 2

14

Explanation for Sample Output 2

It takes $4 to get from bus stop 1 to bus stop 3. It takes $10 to get from bus stop 3 to bus stop 1.

Sample Input 3

5 5 1 3
0 1 5
1 2 3
2 3 2
3 4 1
4 2 4

Sample Output 3

-1

Explanation for Sample Output 3

Although it is possible to get from bus stop 1 to bus stop 3 using $5, there is no way to get from bus stop 3 to bus stop 1.

Tags

Dijkstra, Graph Theory, CS3233 2013 Selection Test

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
120302s256MBMinimum
230302s256MBMinimum
350602s256MBMinimum
4032s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o supplies -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.