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

mrt Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

mrt.html

Problem Description

Assuming you are now hired by SMRT, which manages the Singapore Mass Rapid Transport system. They have employed you, to create an iPhone app for commuters such that it allows them to figure out the travelling distance between 2 MRT stations.

The MRT stations are labelled from 0 to n-1 and there are n MRT stations in total.

SMRT has also provided you with a list of e track segments, which connects different MRT stations together. Each track segment is defined by 3 integers, x, y and t. This indicates that there is a bidirectional track between stations x and y which takes t minutes for trains to travel between them.

Furthermore, your application must also handle Q queries, where each query consists of 2 integers, a and b, where your application must output the travelling distance between MRT station a and b, in minutes.

Do note that the distance from any MRT station to itself, is 0 minutes.

Input

The first line of input consists of 3 integers, n, e and Q

The following e lines will contain x, y and t, defining 1 track segment in each line.

The following Q lines will contain 1 query, consisting of a and b each.

Output

For each query, output the total travelling time between station a and b in minutes, one on each line.

If there is no way for the commuter to travel from a to b, output -1 instead.

Limits

You may assume that n ≤ 200 and Q ≤ 100000.

You may also assume that all t and the answer is ≤ 1000000000.

You may assume that all t are positive integers.

Sample Input

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

Sample Output

3

Tags

Graph Theory, Floyd Warshall

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
12021s32MBMinimum
22021s32MBMinimum
32021s32MBMinimum
42021s32MBMinimum
52021s32MBMinimum
6011s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o mrt -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.