CF1163F.Indecisive Taxi Fee

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

In the city of Capypaland where Kuro and Shiro resides, there are nn towns numbered from 11 to nn and there are mm bidirectional roads numbered from 11 to mm connecting them. The ii -th road connects towns uiu_i and viv_i . Since traveling between the towns is quite difficult, the taxi industry is really popular here. To survive the harsh competition, each taxi company has to find a distinctive trait for their customers.

Kuro is the owner of a taxi company. He has decided to introduce a new fee model for his taxi brand, where the fee for each ride is not calculated based on the trip length, but on the sum of the prices of the roads traveled. The price for each of the mm roads has been decided by Kuro himself.

As of now, the price for the road ii is wiw_i and hence the fee for a taxi ride traveling through roads e1,e2,,eke_1, e_2, \ldots, e_k is i=1kwei\sum_{i=1}^k w_{e_i} .

However, Kuro himself is an indecisive person, so he has drafted qq plans to change the road price. Each of the plans will be based on the original prices wiw_i , except for a single road tjt_j , the price of which is changed to xjx_j . Note, that the plans are independent of each other.

Shiro is a regular customer of the Kuro's taxi brand since she uses the taxi to travel from town 11 to town nn every day. Since she's so a regular customer, Kuro decided to show her all his qq plans before publishing them to the public. Now, Shiro wants to know the lowest fee she must pay to travel from the town 11 to the town nn for each Kuro's plan.

输入格式

The first line contains three integers nn , mm and qq ( 2n21052 \le n \le 2 \cdot 10^5 , 1m,q21051 \le m, q \le 2 \cdot 10^5 ) — the number of towns, the number of roads, and the number of plans that Kuro has drafted respectively.

The ii -th of the next mm contains three integers uiu_i , viv_i and wiw_i ( 1ui,vin1 \le u_i, v_i \le n , 1wi1091 \le w_i \le 10^9 , uiviu_i \ne v_i ) — two endpoints and the original price of the ii -th road.

It is guaranteed, that there is at least one way to travel from town 11 to town nn using these mm bidirectional roads.

Each of the next qq lines contains two integers tjt_j and xjx_j ( 1tjm,1xj1091 \leq t_j \leq m, 1 \leq x_j \leq 10^9 ) — the index of the road Kuro has planned to change and its new price respectively.

输出格式

Print qq integers — the lowest fee Shiro must pay to get from town 11 to town nn in each of those qq plans.

输入输出样例

  • 输入#1

    4 5 6
    1 2 2
    2 4 3
    1 4 7
    1 3 1
    3 4 5
    3 4
    5 1
    3 8
    1 4
    2 1
    3 1
    

    输出#1

    4
    2
    5
    6
    3
    1
    
  • 输入#2

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

    输出#2

    1
    2
    2
    3
    
  • 输入#3

    2 1 1
    1 2 1
    1 3
    

    输出#3

    3
    

说明/提示

In the first example, the original overview of Capypaland looks like this, where the number next to each road denotes the original prices of the roads,

The overview of the first plan,

The lowest fee Shiro must pay in this plan is 44 , which corresponds to the path 141 \rightarrow 4 .

The overview of the second plan,

The lowest fee Shiro must pay in this plan is 22 , which corresponds to the path 1341 \rightarrow 3 \rightarrow 4 .

The overview of the third plan,

The lowest fee Shiro must pay in this plan is 55 , which corresponds to the path 1241 \rightarrow 2 \rightarrow 4 .

首页