好像洛谷的题解都在强调floyd的含义 不能只是背到floyd然后就用 还要理解floyd的含义
f[i][j]：从i号顶点到j号顶点只经过前k号点的最短路程
然后还得有个优化 如果该点作为中转点计算过 那么就不用再走一遍
比较良心的是出题人是大小有顺序地输入
不加那个走过的判断 QAQ我还写错了一个地方
最终
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 const int N=200+5,inf=0x3f3f3f3f; 5 int n,m,q,s,e,t,a[N],f[N][N]; 6 bool u[N]; 7 inline int rd() 8 { 9 int x=0,w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 return w?-x:x; 13 } 14 15 void floyd(int k) 16 { 17 for(int i=0;i<n;i++) 18 for(int j=0;j<n;j++) 19 if(i!=k&&i!=j&&j!=k&&f[i][k]!=inf&&f[k][j]!=inf&&f[i][j]>f[i][k]+f[k][j]) 20 f[i][j]=f[i][k]+f[k][j]; 21 } 22 23 int main() 24 { 25 memset(f,inf,sizeof(f)); 26 n=rd(),m=rd(); 27 for(rg int i=0;i<n;i++) a[i]=rd(); 28 for(rg int i=0;i<m;i++) 29 { 30 int u=rd(),v=rd(),w=rd(); 31 f[u][v]=f[v][u]=min(f[u][v],w); 32 } 33 q=rd(); 34 while(q--) 35 { 36 int now=0; 37 s=rd(),e=rd(),t=rd(); 38 if(a[s]>t||a[e]>t) {printf("-1 ");continue;} 39 while(a[now]<=t&&now<n) 40 { 41 if(!u[now]) floyd(now); 42 u[now]=1; 43 now++; 44 } 45 if(f[s][e]!=inf) printf("%d ",f[s][e]); 46 else printf("-1 "); 47 } 48 return 0; 49 }
