L3-028 Sensen tourism (30 points) (Dijkstra + reverse drawing + details)

I haven't traveled for a long time ！ Sen Sen decided to Z Save travel .

Z Provincial  n  city （ from  1  To  n  Number ） as well as  m  A directed travel route connecting two cities （ For example, self driving 、 The coach 、 train 、 The plane 、 Ship, etc ）, Every time you pass a travel route, you need to pay for the route （ But there may be more than one charging standard , For example, tickets and air tickets are generally not the same price ）.

Z In order to encourage everyone to visit more in the province , Launched The Travel Fund Program ： stay  i  City No. can use  1  Yuan in cash  ai​  Yuan tourist gold （ As long as there is enough cash , You can exchange it unlimited times ）. Transportation between cities can use cash to pay the toll , You can also pay with travel money . say concretely , When passed  j  When traveling on this route , It can be used  cj​  Yuan cash or  dj​  Yuan Travel Fund to pay the fare . Be careful ：  Only one payment method can be selected at a time , You can't use cash and travel money to pay at the same time . But for different lines , Passengers are free to choose different payment methods .

Sen Sen decided to start from  1  Starting from the city of , To  n  Go to city . He's going to prepare some cash before he leaves , And the remaining cash in a city on the way   All   Continue to travel after changing into travel money , Until arrival  n  Up to the city of . Of course , He can also choose to  1  City No. 1 will exchange tourist money , Or complete the journey in cash .

Z The provincial government will adjust the exchange rate according to the participation of each city （ That is, adjust in a city  1  How much travel money can you change in cash ）. Now you need to help Sen calculate , How much cash do you need to carry at least after each adjustment to complete his journey .

Input format :

Input gives three integers on the first line  n,m  And  q（1≤n≤105,1≤m≤2×105,1≤q≤105）, The number of cities in turn 、 The number of travel routes and the number of exchange rate adjustments .

Next  m  That's ok , Each line gives four integers  u,v,c  And  d（1≤u,v≤n,1≤c,d≤109）, Represents a path from  u  The city leads to  v  The directed travel route of city . Each time you pass the line, you need to pay  c  Yuan in cash or  d  Yuan tourist gold . Numbers are separated by spaces . Input guarantee from  1  Starting from the city of , There must be several routes to  n  City No , But there may be more than one travel route between the two cities , Corresponding to different charging standards ; It is also allowed to play inside the city （ namely  u  and  v  identical ）.

In the next line, enter  n  It's an integer  a1​,a2​,⋯,an​（1≤ai​≤109）, among  ai​  At the beginning  i  The city can use  1  Yuan in cash  ai​  A tourist gold . Numbers are separated by spaces .

Next  q  Line describes the adjustment of the exchange rate . The first  i  Line, enter two integers  xi​  And  ai′​（1≤xi​≤n,1≤ai′​≤109）, It means the first one  i  After this exchange rate adjustment ,xi​  The city can use  1  Yuan in cash  ai′​  A tourist gold , While the tourism gold exchange rate of other cities remains unchanged . Please note that ： Each exchange rate adjustment is based on the previous exchange rate adjustment .

Output format :

For each exchange rate adjustment , In the corresponding line, output the minimum amount of cash that Sensen needs to prepare after adjustment , To start from... According to his plan  1  Travel to the city of  n  City No .

Once again remind ： If Sensen decides to exchange tourism money in a city on the way , Then he must put the remaining cash All 、 Disposable exchange , The rest of the trip will be paid entirely with travel money .

sample input :

6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17

sample output :

8
8
1

Sample explanation :

For the first exchange rate adjustment , Sen Sen can follow  1→2→4→6  Route travel , And in  2  Exchange tourist money in City No ;

For the second exchange rate adjustment , Sen Sen can follow  1→2→3→4→6  Route travel , And in  3  Exchange tourist money in City No ;

For the third exchange rate adjustment , Sen Sen can follow  1→3→5→6  Route travel , And in  1  Exchange tourist money in City No .

analysis ： There are unconnected points in this problem , A special sentence is required . Otherwise, you may spend less money because of the large exchange rate, which will affect the result .

Forward mapping 1 To i  Reverse construction n To i.dijkstra Optimize with priority queue and adjacency table .

use map Maintenance minimum .

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int MAX=2e5+9;
map<ll,ll>res;
vector<pair<ll,ll>>cash[MAX/2];
vector<pair<ll,ll>>cre[MAX/2];
ll money[MAX/2];
ll h[MAX/2];
ll n,m,q;
ll vis[MAX/2];
ll dis[MAX/2];
ll diss[MAX/2];
struct node{
    ll order;
    ll d;
    bool operator < (const node &b)const{// Operator overloading , It takes... To put the structure in the priority queue 
        return d>b.d;
    }
};
void dijkstra1(){
    priority_queue<node>q;
    int i,j;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(node{1,0});
    while(!q.empty()){
        ll cur=q.top().order;
        q.pop();
        if(vis[cur]==1)continue;  // I won't join the team again 
        vis[cur]=1;
        for(i=0;i<(int)cash[cur].size();i++){// If it's not connected, you won't join the team 
            if(dis[cash[cur][i].first]>dis[cur]+cash[cur][i].second){
                dis[cash[cur][i].first]=dis[cur]+cash[cur][i].second;
                q.push(node{cash[cur][i].first,dis[cash[cur][i].first]});
            }
        }
    }
    return ;
}
void dijkstra2(){
    memset(vis,0,sizeof(vis));
    priority_queue<node>q;
    int i,j;
    memset(diss,0x3f,sizeof(diss));
    diss[n]=0;
    q.push(node{n,0});
    while(!q.empty()){
        ll cur=q.top().order;
        q.pop();
        if(vis[cur]==1)continue;
        vis[cur]=1;
        for(i=0;i<(int)cre[cur].size();i++){
            if(diss[cre[cur][i].first]>diss[cur]+cre[cur][i].second){
                diss[cre[cur][i].first]=diss[cur]+cre[cur][i].second;
                q.push(node{cre[cur][i].first,diss[cre[cur][i].first]});
            }
        }
    }
    return ;
}
void solve(){
    int x;int y;
    cin>>x>>y;
    if(vis[x]==0){
        res[money[x]]--;
        if(res[money[x]]==0)res.erase(money[x]);
        h[x]=y;
        money[x]=dis[x]+(diss[x]+h[x]-1)/h[x];
        res[money[x]]++;
    }
    cout<<res.begin()->first<<endl;
    return ;
}
int main (){
    cin>>n>>m>>q;
    ll i,j;
    for(i=1;i<=m;i++){
        ll u,v,w1,w2;
        cin>>u>>v>>w1>>w2;
        cash[u].emplace_back(v,w1);
        cre[v].emplace_back(u,w2);// Reverse construction 
    }
    for(i=1;i<=n;i++){
        cin>>h[i];
    }
    dijkstra1();
    dijkstra2();
    memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++){  // Special judgment of disconnected points 
            if(dis[i]==0x3f3f3f3f3f3f3f3f||diss[i]==0x3f3f3f3f3f3f3f3f){
                vis[i]=1;
            }else{
                money[i]=dis[i]+(diss[i]+h[i]-1)/h[i];// The technique of rounding up 
                res[money[i]]++;
            }
           // cout<<money[i]<<" ";//6 8 8 13 17 17
        }
    while(q--){
        solve();
    }
    return 0;
}