传送门

思路:
由于最初的图是存在环的.
因此可以用一个前缀的方式直接求出不使用另外$M$条边时,任意两点之间的最短路.

$$Dist=min(sum-d[y]+d[x],d[y]-d[x])$$

这段代码的意思就是,对于最初的环而言.$x$到$y$的最短路.可以想象成在操场上的两个人,
要么正向靠近,要么反向靠近.

Code：

 for(int i=1;i<=n;i++)
       {
               int x;cin>>x;
               if(i<n)
               {
                       add(i,i+1,x);
                       add(i+1,i,x);
                       d[i+1]=d[i]+x;
               }else add(1,n,x),add(n,1,x);
               sum+=x;
       }

               int x,y;
               cin>>x>>y;
               if(x>y)swap(x,y);
               ll ans=min(sum-d[y]+d[x],d[y]-d[x]);

对于新加入的$M$条边.
假设其影响了$x$到$y$的最短路,则影响一定是$x$要到达影响他的点,再从该点出发去到$y$.

因此在加入$M$条边以后,跑出其他所有点到这$M*2$个点的最短路.

所以对于每个答案,我们考虑最初的最短路和枚举新的信息对初始最短路的影响即可.

Code：

for(int i=0;i<nums.size();i++)dijkstra(i);
for(int i=0;i<nums.size();i++)ans=min(ans,dist[x][i]+dist[y][i]);

注意:

• 对于$M$个点需要离散化.否则会超内存
• 其次本题对于空间要求较高,开空间的时候要精确一些.
• 不要忘记开ll

时间复杂度$O(M* N * \log N+q * M)$

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
using namespace std;
typedef long long ll;
typedef pair<ll,int>PII; 
typedef unsigned long long ull;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=52501+10;
const int M=N*2+40;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll d[N];
bool vis[N];
ll dist[N][40];
int e[M],ne[M],h[N],idx,w[M];
vector<int>nums;
void add(int a,int b,int c)
{
        e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra(int st)
{
        memset(vis,false,sizeof vis);
        priority_queue<PII,vector<PII>,greater<PII>>q;
        dist[nums[st]][st]=0;
        q.push({dist[nums[st]][st],nums[st]});
        while(!q.empty())
        {
                auto t=q.top();q.pop();
                int ver=t.second;
                if(vis[ver])continue;
                vis[ver]=true;
                for(int i=h[ver];~i;i=ne[i])
                {
                        int j=e[i];
                        if(dist[j][st]>dist[ver][st]+w[i])
                        {
                                dist[j][st]=dist[ver][st]+w[i];
                                q.push({dist[j][st],j});
                        }
                }
        }
}
void solve()
{
       memset(dist,llinf,sizeof dist);
       memset(h,-1,sizeof h);
       int n,m;
       cin>>n>>m;
       ll sum=0;
       for(int i=1;i<=n;i++)
       {
               int x;cin>>x;
               if(i<n)
               {
                       add(i,i+1,x);
                       add(i+1,i,x);
                       d[i+1]=d[i]+x;
               }else add(1,n,x),add(n,1,x);
               sum+=x;
       }
       while(m--)
       {
               int x,y,z;
               cin>>x>>y>>z;
               add(x,y,z),add(y,x,z);
               nums.push_back(x),nums.push_back(y);
       }
       sort(nums.begin(),nums.end());
       nums.erase(unique(nums.begin(),nums.end()),nums.end());
       for(int i=0;i<nums.size();i++)dijkstra(i);
       int q;cin>>q;
       while(q--)
       {
               int x,y;
               cin>>x>>y;
               if(x>y)swap(x,y);
               ll ans=min(sum-d[y]+d[x],d[y]-d[x]);
               for(int i=0;i<nums.size();i++)ans=min(ans,dist[x][i]+dist[y][i]);
               cout<<ans<<endl;
       }
       return ;

}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}