有n个节点的m条无向边的图，节点编号为1~n
然后有点权和边权，给出q个询问，每一个询问给出2点u，v
输出u，v的最短距离
这里的最短距离规定为：
u到v的路径的所有边权+u到v路径上最大的一个点权的和（点权也可以是u，v）
n<=1000
m<=20000
Q<=20000
时限：5000ms
没有点权的话，好处理
加了点权呢？
我们可以先枚举n个节点，跑n次spfa，当枚举节点u时，我们默认节点u是所有路径上点权最大的一个点
即我们枚举节点u时，我们先把点权比u大的节点删除了，在剩下的图跑spfa
但实际上只要在spfa时加一句判断即可，并不用真的去重建图
这样对于每一个询问，我们只要枚举点权最大的点就可以了，每一个询问是Q(n)
ans=min(dis[i][u]+dis[i][v]+cost[i])
但是这样我还是tle了， 因为这样需要开一个2维数组
dis[i][j]表示以第i个点为起点，到达节点j的短路
最后选择先存下所有询问，离线更新ans，在spfa的同时枚举更新
为什么这样就可以了呢？
因为一维数组比二维数组快很多。
从这道题：
1.当点权和边权混在一起比较难求的时候，我们可以先假设点权最大，分离出点权和边权，再枚举每一个点，就可以了
不止这个， 枚举的思想在很多时候都很好用
2.用stl的queue，时间是4000ms左右，用自己的队列，时间是3500左右，快了半秒
3.一维数组的访问比二维数组快很多
4.做题的时候要注意，循环的时候的终止条件，是到n? m? 还是Q?这个写错就wa了，又难发现
#include<cstdio>
#include<cstring>
#include<algorithm> #define ll long long using namespace std; const int maxn=;
const int maxm=+;
const ll inf=0x3f3f3f3f3f3f3f3f; struct Edge
{
int to,next;
ll w;
};
Edge edge[maxm<<];
int head[maxn];
int tot;
int que[maxm<<];
ll ans[maxm];
int a[maxm];
int b[maxm];
ll dis[maxn];
ll cost[maxn];
bool vis[maxn];
int n,Q; void init()
{
memset(head,-,sizeof head);
tot=;
} void addedge(int u,int v,ll w)
{
edge[tot].to=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
} void solve(); int main()
{
int m;
while(scanf("%d %d",&n,&m)){
if(!n&&!m)
break; for(int i=;i<=n;i++)
scanf("%lld",&cost[i]);
int u,v;
ll w;
init();
for(int i=;i<=m;i++){
scanf("%d %d %lld",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
scanf("%d",&Q);
for(int i=;i<=Q;i++){
scanf("%d %d",&a[i],&b[i]);
} solve();
}
return ;
} void spfa(int srt)
{
for(int i=;i<=n;i++)
dis[i]=inf;
dis[srt]=;
memset(vis,false,sizeof vis);
int l=,r=;
que[r++]=srt;
vis[srt]=true;
while(l<r){
int u=que[l++];
vis[u]=false;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to;
ll w=edge[i].w;
if(cost[v]>cost[srt])
continue;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
que[r++]=v;
vis[v]=true;
}
}
}
}
for(int i=;i<=Q;i++){
if(dis[a[i]]==inf||dis[b[i]]==inf)
continue;
if(dis[a[i]]+dis[b[i]]+cost[srt]<ans[i])
ans[i]=dis[a[i]]+dis[b[i]]+cost[srt];
}
} void solve()
{
for(int i=;i<=Q;i++)
ans[i]=inf;
for(int i=;i<=n;i++){
spfa(i);
} for(int i=;i<=Q;i++){
if(ans[i]==inf)
printf("-1\n");
else
printf("%lld\n",ans[i]);
}
printf("\n"); return ;
}