L3-028 森森旅游 (30 分)

题目描述：

n个城市，你要从1跑到n，每条路都有两种支付方式，一种是现金，一种是旅游币，你现在从1出发，初始有x块现金，可以选择在一个城市的将所有的现金换成旅游币，在这个城市之前，只能用现金支付，在这个城市之后只能用旅游币支付。

给出每个城市的汇率，即一块钱可以换多少旅游币

q次询问，每次询问，会改变城市x的汇率为c,问现在最少需要在起点准备多少现金可以到达n

且每次汇率调整都是在上一次汇率调整的基础上进行的

思路：

首先正向以现金建图，跑出i到n的最短路dis

再反向以旅游币建图，跑出n到i的最短路diss

现在我们就可以计算以每个城市为中转站转换货币的情况下，最少需要准备的现金数量: $dis[i] + \frac{diss[i] + hui[i] - 1}{hiu[i]}$

我们只需要维护一个数据结构，能满足：

• 求最小值
• 删除
• 增加

我这里用的是map

因为不喜欢在参数里面传数字，所以代码写的很啰嗦

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define int long long
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 100000 + 50
int n, m, k, x;
int u, v, c, cc;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[300005];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tott;
int headd[MAX];
ran trr[300005];
inline void addd(int u, int v, int c){
    trr[++tott].to = v;
    trr[tott].val = c;
    trr[tott].nex = headd[u];
    headd[u] = tott;
}

int dis[MAX];
bool vis[MAX];
void dijkstra1(){
    priority_queue<pii, vector<pii>, greater<pii> >q;
    q.push(m_p(0, 1));
    for(int i = 1; i <= n; ++i)dis[i] = 1e18;
    dis[1] = 0;
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
}

int diss[MAX];
void dijkstra2(){
    priority_queue<pii, vector<pii>, greater<pii> >q;
    q.push(m_p(0, n));
    mem(vis, 0);
    for(int i = 1; i <= n; ++i)diss[i] = 1e18;
    diss[n] = 0;
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = headd[u]; i; i = trr[i].nex){
            int v = trr[i].to;
            if(diss[v] > diss[u] + trr[i].val){
                diss[v] = diss[u] + trr[i].val;
                q.push(m_p(diss[v], v));
            }
        }
    }
}
int hui[MAX];
int ans[MAX];
void work(){
    cin >> n >> m >> k;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> c >> cc;
        add(u, v, c);
        addd(v, u, cc);
    }
    dijkstra1();
    dijkstra2();
    mem(vis, 0);
    map<int, int>mp;
    for(int i = 1; i <= n; ++i){
        cin >> hui[i];
        if(dis[i] > 1e15 || diss[i] > 1e15){
            vis[i] = 1;
        }
        else{
            ans[i] = dis[i] + (diss[i] + hui[i] - 1) / hui[i];
            ++mp[ans[i]];
        }
    }
    while (k--) {
        cin >> x >> c;
        if(!vis[x]){
            --mp[ans[x]];
            if(mp[ans[x]] == 0)mp.erase(ans[x]);
            hui[x] = c;
            ans[x] = dis[x] + (diss[x] + c - 1) / c;
            ++mp[ans[x]];
        }
        cout << mp.begin()->first;
        if(k)cout << endl;
    }
}


signed main(){
    work();
    return 0;
}