题目链接：

https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652364

题解：

建两个图，正图和反图。

正图里的边权是现金，反图里的边权是旅游金。

然后分别以1为起点在正图上跑最短路，以n为起点在反图上跑最短路。

这样计算出每个点的答案，取最小，不带修改的情况就做完了。

带修改的情况放线段树上维护一下就好了。

注意巨大坑点：不保证图连通。

参考链接：

https://www.cnblogs.com/zhanglichen/p/14726600.html

代码：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;

struct node
{
    ll to,val;
};
vector<node>v_mon[200500],v_bi[200500];
ll a[200500]= {0};


struct node1
{
    ll now,val;
    bool operator <(const node1& a) const
    {
        return val>a.val;
    }
};
priority_queue<node1>que1,que2;
ll dis_mon[200500]= {0},dis_bi[200500]= {0};


ll tree[800500]= {0};
ll min1[800500]= {0};
ll val[800500]= {0};
void push_up(ll n)
{
    min1[n]=min(min1[2*n],min1[2*n+1]);
}
void build(ll n,ll l,ll r)
{
    if(l==r)
    {
        min1[n]=tree[n]=val[l];
        return ;
    }
    ll mid=(l+r)/2;
    build(2*n,l,mid);
    build(2*n+1,mid+1,r);
    push_up(n);
}
void update(ll n,ll L,ll R,ll pos,ll val1)
{
    if(L==R&&L==pos)
    {
        min1[n]=tree[n]=val1;
        return ;
    }
    ll mid=(L+R)/2;
    if(pos<=mid)
        update(2*n,L,mid,pos,val1);
    else
        update(2*n+1,mid+1,R,pos,val1);
    push_up(n);
}
int main()
{
    ll n,m,k,from,to,val1,val2,pos;
    scanf("%lld%lld%lld",&n,&m,&k);

    for(ll i=1; i<=n; i++)
        dis_mon[i]=inf,dis_bi[i]=inf;

    dis_mon[1]=0,dis_bi[n]=0;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld%lld%lld%lld",&from,&to,&val1,&val2);
        v_mon[from].push_back({to,val1});
        v_bi[to].push_back({from,val2});
    }

    que1.push({1,0});
    while(!que1.empty())
    {
        ll now=que1.top().now,val=que1.top().val;
        que1.pop();
        for(node i:v_mon[now])
        {
            if(dis_mon[i.to]>val+i.val)
            {
                dis_mon[i.to]=val+i.val;
                que1.push({i.to,dis_mon[i.to]});
            }
        }
    }

    que2.push({n,0});
    while(!que2.empty())
    {
        ll now=que2.top().now,val=que2.top().val;
        que2.pop();
        for(node i:v_bi[now])
        {
            if(dis_bi[i.to]>val+i.val)
            {
                dis_bi[i.to]=val+i.val;
                que2.push({i.to,dis_bi[i.to]});
            }
        }
    }

    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);

    for(ll i=1; i<=n; i++)
    {
        if(dis_mon[i]==inf||dis_bi[i]==inf)
            val[i]=inf;
        else
            val[i]=dis_mon[i]+dis_bi[i]/a[i]+(ll)((dis_bi[i]%a[i])>0?1:0);
    }

    build(1,1,n);

    for(ll i=1; i<=k; i++)
    {
        scanf("%lld",&pos);
        scanf("%lld",&a[pos]);
        if(dis_mon[pos]==inf||dis_bi[pos]==inf)
            val[pos]=inf;
        else
            val[pos]=dis_mon[pos]+dis_bi[pos]/a[pos]+(ll)((dis_bi[pos]%a[pos])>0?1:0);
        update(1,1,n,pos,val[pos]);
        printf("%lld\n",min1[1]);
    }
}