【牛客网】

知识框架

No.1 前缀和

NC14556：数圈圈

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001000
long long n,m,t,k,d;
long long x,y,z;
char ch;
string str;
vector<int>v[N];
int num[10]={1,0,0,0,1,0,1,0,2,1}; //0~9
int onum[N+1];
int s[N+1];
void Init(){for(int i=1;i<=N;i++){str=to_string(i);for(auto ss:str){int num1=ss-'0';onum[i]+=num[num1];}}s[1]=0;for(int i=2;i<=N;i++){s[i]=s[i-1]+onum[i];}
}
int main()
{Init();cin>>n;for(int i=0;i<n;i++){cin>>x>>y;cout<<s[y]-s[x-1]<<endl;}return 0;
}

NC14600：珂朵莉与宇宙

//巧妙地利用求平方 变化为减去平方看差是否存在：
//通过指针的指向，那么一串数组中的任意子区间就可以用 两个前缀和 进行 相减 得到：#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1];int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}int res=0;int cnt[N];cnt[0]=1;    //前缀和为0的表示 直接前面n个为平方和了//以每一个右边的端点为指针for(int i=1;i<=n;i++){//找到所有可能的平方和：//处理第i个前缀和的所有完全平方数for(int j=0;j*j<=s[i];j++){c=s[i]-j*j;         //假设前面有前缀和==c的； 即if(cnt[c]>0){       //如果前面有前缀和==c的 代表有子区间为j*j；res+=cnt[c];}}cnt[ s[i] ]++;   // 已处理过的这个端点，加入到cnt里面  表示前面的 前缀和为s[i] 的前缀和的个数加一}cout<<res;return 0;
}

NC21195 ：Kuangyeye and hamburgers

//vector 的 排序 比如降序：  sort(v.rbegin(),v.rend());
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1]={0};int main()
{cin>>n>>m;vector<int>ans;for(int i=1;i<=n;i++){cin>>x;ans.push_back(x);}sort(ans.rbegin(),ans.rend());for(int i=0;i<ans.size();i++){s[i+1]=s[i]+ans[i];}int res=0;while(m--){cin>>x>>y;res=max(res,s[y]-s[x-1]);}cout<<res<<endl;return 0;
}

NC19798：区间权值

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1]={0};
int w[N+1];
int leijia(int l,int r){return (s[r]-s[l-1])*w[r-l+1];
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}for(int i=1;i<=n;i++){cin>>w[i];}//下面这个双层循环了导致时间复杂度很高：long long res=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){res=res+leijia(i,j);}}//将 j 的那部分再进行前缀和：因此要把过程改写：for(int j=1;j<=n;j++){}cout<<res%(1000000000+7);return 0;
}

NC16730：run

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=1e5+5;
long long n,m,t,k,d,q;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
const int  mod=1e9+7;
// 这里的结果如果是  dp[N][3]  就会出错：
long long dp[N][2],ans[N];
int main()
{cin>>q>>k;dp[0][0]=1;for(int i=1;i<=N;i++){dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod; //以走一米的方式走到i米的时候，可能情况只能是走i-1米的情况总和；if(i-k>=0){dp[i][1]=dp[i-k][0];                 // because not can continue two meters run；only one 情况}ans[i]=(ans[i-1]+dp[i][0]+dp[i][1])%mod;}for(int i=1;i<=q;i++){cin>>x>>y;cout<<(ans[y]-ans[x-1]+mod)%mod<<endl;}return 0;
}// 下面是正确的：
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5;
const int M = 1e9 + 7;int dp[N][2], s[N];int main() {int q, k, l, r;scanf("%d%d", &q, &k);dp[0][0] = 1;for (int i = 1; i <= N; i++) {dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % M;if (i >= k) {dp[i][1] = dp[i - k][0];}s[i] = (s[i - 1] + dp[i][0] + dp[i][1]) % M;}while (q--) {scanf("%d%d", &l, &r);printf("%d\n", (s[r] - s[l - 1] + M) % M);}return 0;
}

NC15035：送分了qaq

经典基础：对x经行分位数处理，直到没有位数

#include<stdio.h>
int check(int x)
{int t=0;while(x > 0)//对x经行分位数处理，直到没有位数{if(x % 10 == 3){return 1；//如果已经有1接下来的位数便不用再判断了，直接可以return 1了}x /= 10;}return 0;
}

#include <stdio.h>
int main()
{int m,n;while(scanf("%d%d",&n,&m)!=EOF){if (m == 0 && n == 0)break;int ans=0;for(int i=n;i<=m;i++){int x=i;while(x){if(x%10==4||x%100==38) {ans++;break;}x/=10;}}printf("%d\n",ans);}} 

No.2 字符串：

初始模板：

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {return 0;
}

小知识点：

str.substr(i,n) : 注意不能越界；； 必须判断以下跳出

基于KMP算法的字符串匹配：

暴力搜索：

• 暴力算法：自己的想法；就是找到第一个相匹配之后就直接转换对象看小字符串去，就想那个断痕那个，先确定小字符串大小然后for便利到该大小记得加循环跳出时间，还有就是字符串可以substr（应该会快一点吗？）

AC自动机：

字符串hash：

后缀自动机：

No.3 栈

NC15029：吐泡泡

//全对的
#include<iostream>
#include<string>
#include<stack>using namespace std;int main()  // stack 写法
{string str;while(cin >> str){stack<char> st, sk; for(auto ch : str){if(st.size()){auto top = st.top();bool flag = 1;while(ch == top){if(ch == 'o'){st.pop();ch = 'O';  }else{st.pop();flag = 0;break;}if(!st.size()) break;top = st.top();}if(flag) st.push(ch);}else{st.push(ch);}}//输出while(st.size()){sk.push(st.top());st.pop();}while(sk.size()){cout << sk.top();sk.pop();}puts("");}return 0;
}//  对了 百分之四十。
//对于N要进行适应性的更改，对于字段错误#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define N 100100int n,m,k,g,d;int x,y,z;char ch;string str;int main() {cin>>str;stack<char>b;vector<char>a;for(auto i:str){a.push_back(i);}for(int i=0;i<a.size();i++){if(b.size()>0){char ss;ss=b.top();if(ss==a[i]&&ss=='o'){b.pop();a[i]='O';i--;}else if(ss==a[i]&&ss=='O'){b.pop();}else{b.push(a[i]);}}else{b.push(a[i]);}}vector<char>c;while(!b.empty()){c.push_back(b.top());b.pop();}reverse(c.begin(),c.end());for(auto i:c){cout<<i;}return 0;}

NC50998：括号画家

例如 (){} 是美观的括号序列，而 )({)[}]( 则不是。

思路：就是先用i指针 指着开始部位。  再有j指针循环以i起头的可能。//对于N要进行适应性的更改，对于字段错误#include<bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define N 100100int n,m,k,g,d;int x,y,z;string str;int main() {cin>>str;int res=0;//类似双指针了好像；for(int i=0;i<str.size();i++){stack<char>st;for(int j=i;j<str.size();j++){if(str[j]=='['){st.push(']');}else if(str[j]=='{'){st.push('}');}else if(str[j]=='('){st.push(')');}else if(st.empty() || str[j]!=st.top()){//夭折break;}else{st.pop();//清空代表在此刻是 对称的。if(st.empty())res=max(res,j-i+1);}}}cout<<res<<endl;return 0;}

NC15975：小c的记事本

// 自己用 char
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {ios::sync_with_stdio(false);cin>>n;stack<vector<char>>ans;vector<char>st;while(n--){cin>>x;if(x==1){ans.push(st);cin>>str;for(auto p:str){st.push_back(p);}}else if(x==2){ans.push(st);cin>>k;while(k--){st.pop_back();}}else if(x==3){cin>>k;cout<<st[k-1]<<endl;}else if(x==4){st=ans.top();ans.pop();}}return 0;
}// 别人用 string
#include<bits/stdc++.h>
using namespace std;
int main()
{ios::sync_with_stdio(false);int t;while(cin>>t){stack<string>s; //定义一个字符串类型的栈 int a;string s1;s.push("");while(t--){cin>>a;if(a==1){cin>>s1;s.push(s.top()+s1); //向记事本插入字符串 }else if(a==2){int k;cin>>k;s1=s.top();s.push(s1.substr(0 , s1.length()-k));}else if(a==3){int k;cin>>k;s1=s.top();cout<<s1[k-1]<<endl; } else s.pop();}}return 0;
}

NC14666：最优屏障

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int num(vector<int>h , int l, int r){if(l==r)return 0;int res=0;int maxx=0;for(int i=l;i<=r;i++){maxx=0;for(int j=i+1;j<=r;j++){if(maxx<min(h[i-1],h[j-1]))res++;maxx=max(maxx,h[j-1]);}}return res;}
int main() {cin>>t;for(int i=1;i<=t;i++){cin>>n;vector<int>h;for(int j=0;j<n;j++){cin>>x;h.push_back(x);}int sum=num(h,1,n);vector<int>cnt;cnt.push_back(0);cnt.push_back(0);for(int j=2;j<=n;j++){int zuo=num(h,1,j-1);int you=num(h,j,n);cnt.push_back(sum-zuo-you);}int maxxx=0;int weizhi=0;for(auto p:cnt)maxxx=max(maxxx,p);for(int j=0;j<cnt.size();j++){if(cnt[j]==maxxx){weizhi=j;break;}}cout<<"Case #"<<i<<": "<<weizhi<<" "<<maxxx<<endl;}   return 0;
}

NC14847：Masha与老鼠：

NC50999：表达式计算

#include<bits/stdc++.h>using namespace std;
char s[50];
stack<int>s1;
stack<char>s2;int level(char op){if(op=='+'||op=='-')return 1;else if(op=='*'||op=='/')return 2;else if(op=='^')return 3;return 0;
}int Pow(int a,int b){int res=1;while(b--){res*=a;}return res;
}void calc(char op){int x,y;x=s1.top();s1.pop();y=s1.top();s1.pop();if(op=='+')s1.push(x+y);else if(op=='-')s1.push(y-x);else if(op=='*')s1.push(x*y);else if(op=='/')s1.push(y/x);else if(op=='^')s1.push(Pow(y,x));
}int main(){cin>>s+1;int n=strlen(s+1),num=0;s1.push(0);for(int i=1;i<=n;i++){if(s[i]>='0'&&s[i]<='9'){num=num*10+s[i]-'0';if(s[i+1]<'0'||s[i+1]>'9'){s1.push(num);num=0;}continue;}if(s[i]=='('){s2.push(s[i]);}else{if(s[i]==')'){while(!s2.empty()&&s2.top()!='('){calc(s2.top());s2.pop();}if(!s2.empty()&&s2.top()=='(')s2.pop();}else{while(!s2.empty()&&level(s[i])<=level(s2.top())){calc(s2.top());s2.pop();}s2.push(s[i]);}}}while(!s2.empty()&&s2.top()!='('&&s2.top()!=')'){calc(s2.top());s2.pop();}cout<<s1.top()<<endl;return 0;
}

No.4 最短路径

最短路算法详解_weixin_34018202的博客-CSDN博客

1：两种存储方式：因为邻接表没有 前向星可观，所以 ：邻接矩阵+前向星

NC14501：大吉大利，晚上吃鸡：最短路+动态规划

Bellman-Ford算法

Dijkstra算法/Dijkstra + 优先队列的优化

NC20131：飞行路线

//这个k层免费 不是简单的先找到最短，然后去掉k个最大的；

floyd-Warshall算法

SPFA

1：链式前向星：

其中edge[ ] .to表示第i条边的终点, edge[i] .next表示与第i条边同起点的下一条边的存储位置,edge[i] .w为边权值.
另外还有一个数组head[ ],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实
在以i为起点的所有边的最后输入的那个编号．
head[]数组一般初始化为-1,对于加边的add函数是这样的:

下面是对链式前向星的讲解：注意那个 head[u] = cnt++;//更新以u为起点上一条边的编号 是先赋值，再 累加的；

链式前向星–最通俗易懂的讲解_sugarbliss的博客-CSDN博客_链式前向星

NC14369：最短路：很直接

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int mp[2000+1][20000+1];
int vis[N];
int dist[N];
int to[N],w[N],head[N]={-1},ne[N],idx=0;
//vis数组标记了节点v是否在Q中
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x]; //这条边的上一条边head[x]=idx++;     // 这个点的最后一条边为： idx表示边
}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[1]=0;vis[1]=1;queue<int>q;q.push(1);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){//遍历以x为起点的所有的边；toint i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}
}int main() {memset(head,-1,sizeof(head));cin>>n>>m;while(m--){cin>>x>>y>>z;add(x,y,z);}spfa();for(int i=2;i<=n;i++){cout<<dist[i]<<endl;}return 0;
}

NC15522：武 ：很直接

//注意 链式前向星的 如果是无向图 需要两次 add  且 数据的N边数要乘以2
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N];
int to[N*2],head[N*2]={-1},ne[N*2],w[N*2];//这个因为是无向图；双向
int idx=0;
int p;
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}
}
int main() {memset(head,-1,sizeof(head));cin>>n>>p>>k;for(int i=1;i<=n-1 ;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}spfa();sort(dist+1,dist+1+n);cout<<dist[k+1]<<endl;//离得最短的是本身为0的return 0;
}

NC15549：小木乃伊到我家

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N];
int to[N*2],head[N*2]={-1},ne[N*2],w[N*2];//这个因为是无向图；双向
int idx=0;
int p;
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}}
int main() {memset(head,-1,sizeof(head));cin>>n>>m;p=1;//出发点while(m--){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}spfa();if(dist[n]==inf)cout<<"qwb baka"<<endl;else cout<<dist[n]<<endl;return 0;
}

NOI1997：最优乘车

对于：stringstream ss 等的用法；；

int main(){string s = "1 23 # 4";stringstream ss;ss<<s;while(ss>>s){cout<<s<<endl;int val = convert<int>(s);cout<<val<<endl;}return 0;
}
输出：1 1 23 23 # 0 4 4

//第一种方法：用bfs 函数类似;//第二种类比距离：该条路线距离为0  换乘一次能达到的为距离为1 的点；所以最终结果要-1；下面用的是这个
// 类比化距离；；
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]={-1},ne[N*2],w[N*2];//这个因为是无向图；双向
int idx=0;
int p;//开始的地方：
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}}
int main() {memset(head,-1,sizeof(head));cin>>m>>n;getchar();while(m--){getline(cin,str);stringstream ssin(str);int cnt=0;while(ssin>>p)stop[cnt++]=p;for(int i=0;i<cnt;i++){for(int j=i+1;j<cnt;j++){add(stop[i],stop[j],1);}}}p=1;//开始spfa();if(dist[n]==inf)cout<<"NO"<<endl;else cout<<dist[n]-1<<endl;return 0;
}

NC22947：香甜的黄油

//问题是：图中已经确定的几点到 图中某一点的最短距离；
// 即 dist[c1]+dist[c2]+...+dist[cn]//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,c[N],g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]={-1},ne[N*2],w[N*2];//这个因为是无向图；双向
int idx=0;
int p;//开始的地方：
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}}
int main() {memset(head,-1,sizeof(head));int res=inf;cin>>d>>n>>m;for(int i=1;i<=d;i++){cin>>c[i];}while(m--){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}for(int i=1;i<=n;i++){//以i为起点p=i;spfa();int num=0;for(int j=1;j<=d;j++){num+=dist[c[j]];}res=min(res,num);}cout<<res<<endl;return 0;
}

NC17511：公交线路

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,c[N],g,s,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]={-1},ne[N*2],w[N*2];//这个因为是无向图；双向
int idx=0;
int p;//开始的地方：
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}}
int main() {memset(head,-1,sizeof(head));cin>>n>>m>>s>>d;p=s;while(m--){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}spfa();if(dist[d]==inf)cout<<0<<endl;else cout<<dist[d]<<endl;return 0;
}

NC14292：Travel

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,q,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dist[N],vis[N];
int to[N*5],head[N*5]={-1},ne[N*5],w[N*5];//这个因为是无向图；双向
int idx=0;
int p;
void add(int x,int y,int z){to[idx]=y;w[idx]=z;ne[idx]=head[x];head[x]=idx++;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]=0;vis[p]=1;queue<int>q;q.push(p);while(q.size()){x=q.front();q.pop();vis[x]=0;for(int j=head[x];j!=-1;j=ne[j]){int i=to[j];if(dist[i]>dist[x]+w[j]){dist[i]=dist[x]+w[j];if(vis[i]==0){q.push(i);vis[i]=1;}}}}}
int main() {memset(head,-1,sizeof(head));cin>>n>>m;for(int i=1;i<=n;i++){if(i==n){cin>>x;add(i,1,x);add(1,i,x);}else{cin>>x;add(i,i+1,x);add(i+1,i,x);}}for(int i=1;i<=m;i++){cin>>x>>y>>z;if(x==y)continue;add(x,y,z);add(y,x,z);}cin>>q;while(q--){cin>>x>>y;p=x;spfa();cout<<dist[y]<<endl;}return 0;
}///-------------------------------------------
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
using namespace std;
const int N=52501+10,M=22;
ll n,m,q,x,y;
ll p[N],dist[N][M<<1];
int d[N],h[N],tot,door[M<<1];
bool st[N];
struct node{int to,nxt,k;
}e[N*2];
void add(int u,int v,int w){e[++tot].to=v;e[tot].nxt=h[u];e[tot].k=w;h[u]=tot;
}
void dijkstra(int x){int s=door[x];dist[s][x]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({s,0});while(heap.size()){int u=heap.top().first;heap.pop();for(int i=h[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(dist[v][x]>dist[u][x]+e[i].k){dist[v][x]=dist[u][x]+e[i].k;heap.push({v,dist[v][x]});}}}
}
int main(){cin>>n>>m;memset(h,-1,sizeof h);memset(dist,0x3f,sizeof dist);for(int i=1;i<=n;++i) cin>>d[i],p[i]=p[i-1]+d[i];for(int i=1;i<n;++i){add(i,(i+1),d[i]);add((i+1),i,d[i]);}add(1,n,d[n]),add(n,1,d[n]);int nd=0;for(ll i=1,u,v,w;i<=m;++i){cin>>u>>v>>w;add(u,v,w),add(v,u,w);door[++nd]=u,door[++nd]=v;}sort(door+1,door+1+nd);nd=unique(door+1,door+1+nd)-(door+1);for(int i=1;i<=nd;++i)dijkstra(i);cin>>q;while(q--){cin>>x>>y;ll len=abs(p[x-1]-p[y-1]);ll ans=min(len,p[n]-len);for(int i=1;i<=nd;++i)ans=min(ans,dist[x][i]+dist[y][i]);cout<<ans<<endl;}return 0;
}