题目描述

题目还是看链接吧,好长

样例

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

算法

(最短路+multiset) $O(mlongn)$

跑两遍最短路,dist1求得是从起点到某个点i需要的钱,dist2求得是从某个点i到终点所需要
的旅游金!!于是总需要的钱为dist1[i]+(dist2[i]+d[i]-1)/d[i],注意上取整!!
然后最后把所有可以的到达n的路径需要的钱放入multiset就好,multiset大法好

参考文献

https://www.bilibili.com/read/cv11044423?from=search

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long, int> pli;
typedef long long ll;
const int N =1e5+10,M=2e5+10;
const long long inf=2e18;
int h1[N],e1[M],ne1[M],idx1,w1[M];
int h2[N],e2[M],ne2[M],idx2,w2[M];
ll ans[N];
multiset<long long>s;
int d[N];//旅游金
int n,m,t;
bool st[N];
void add1(int a,int b,int c)//正向边
{
    e1[idx1]=b,w1[idx1]=c,ne1[idx1]=h1[a],h1[a]=idx1++;
}
void add2(int a,int b,int c)//反向边
{
    e2[idx2]=b,w2[idx2]=c,ne2[idx2]=h2[a],h2[a]=idx2++;
}
void dijkstra(int st1,ll dist[],int w[],int h[],int e[],int ne[])
{
      memset(st,0,sizeof st);
      priority_queue<pli,vector<pli>,greater<pli> >heap;
      for(int i=1;i<N;i++)  dist[i]=inf;//ll的初始化为正无穷

      heap.push({0,st1});
      dist[st1]=0;
      while(heap.size())
      {
         auto t=heap.top();
         heap.pop();
         ll a=t.first;//边长
         int b=t.second;//点
         if(st[b])  continue;
         st[b]=true;
         for(int i=h[b];i!=-1;i=ne[i])
         {
              int j=e[i];
              if(dist[j]>a+w[i])
              {
                dist[j]=a+w[i];//更新
                heap.push({dist[j],j});
              }
         }
      }

 }
 //支持一个修改操作
int main()
{
    ll dist1[N],dist2[N];
    scanf("%d%d%d", &n,&m,&t);
    memset(h1,-1,sizeof h1);
    memset(h2, -1, sizeof h2);
    while(m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d", &a, &b,&c,&d);
        add1(a,b,c),add2(b,a,d);
    }
    dijkstra(1,dist1,w1,h1,e1,ne1);//起点的最短路
    dijkstra(n,dist2,w2,h2,e2,ne2);//终点的最短路
    for(int i=1;i<=n;i++)   scanf("%d",&d[i]);//旅游金
    for(int i=1;i<=n;i++)
    {
        //i是从1到的点用钱买
        if(dist1[i]!=inf&&dist2[i]!=inf)
        {

            ans[i]=dist1[i]+(dist2[i]+d[i]-1)/d[i];//上取整,后面是用旅游金换
            s.insert(ans[i]);
        }
    }
    while(t--)
    {
        int a,b;
        scanf("%d%d", &a, &b);
        d[a]=b;
        if(dist1[a]!=inf&&dist2[a]!=inf)
        {
            s.erase(s.find(ans[a]));
            ans[a]=dist1[a]+(dist2[a]+d[a]-1)/d[a];
            s.insert(ans[a]);
        }
        printf("%lld\n",*s.begin());
    }

    return 0;
}