有n个节点的m条无向边的图，节点编号为1~n
然后有点权和边权，给出q个询问，每一个询问给出2点u，v
输出u，v的最短距离
最短距离 = u到v的路径的所有边权 + u到v路径上最大的一个点权（点权也可以是u，v）
n<=1000
m<=20000
Q<=20000
时限：5000ms
#include <iostream> #include <cstring> #include <vector> #include <cstdio> #define MAXN 1005 #define MAXM 40005 #define inf 0x3f3f3f3f3f3f3f3f using namespace std; int head[MAXN]; int cnt=0; int n,m; long long val[MAXN]; int qua[MAXM],qub[MAXM]; int q; long long ans[MAXM]; int vis[MAXN]; long long dis[MAXN]; int mystack[MAXM*5]; struct Node { int v; long long w; int next; }edge[MAXM]; void init() { cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,long long w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void spfa(int start) { for(int i=0;i<=n+3;i++) vis[i]=0,dis[i]=inf; vis[start]=1; dis[start]=0; int h=0,r=0; mystack[r++]=start; while(h<r) { int top=mystack[h++]; vis[top]=0; for(int i=head[top];i!=-1;i=edge[i].next) { int v=edge[i].v; if(val[v]<=val[start]&&dis[v]>dis[top]+edge[i].w) { dis[v]=dis[top]+edge[i].w; if(!vis[v]) { mystack[r++]=v; vis[v]=1; } } } } for(int i=1;i<=q;i++) { int u=qua[i]; int v=qub[i]; if(dis[u]!=inf&&dis[v]!=inf&&ans[i]>dis[u]+dis[v]+val[start]) ans[i]=dis[u]+dis[v]+val[start]; } } int main() { int u,v; long long w; while(scanf("%d%d",&n,&m)==2) { if(n==0&&m==0)break; init(); for(int i=1;i<=n;i++) scanf("%lld",&val[i]); for(int i=1;i<=m;i++) { scanf("%d%d%lld",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } scanf("%d",&q); for(int i=1;i<=q;i++) scanf("%d%d",&qua[i],&qub[i]),ans[i]=inf; for(int i=1;i<=n;i++) spfa(i); for(int i=1;i<=q;i++) { if(ans[i]==inf) printf("-1\n"); else printf("%lld\n",ans[i]); } printf("\n"); } return 0; }