一道好題，然而看題解做的......
floyed的實質：只經過前k個點i到j的最短路，原狀態轉移方程為
f [ k ] [ i ] [ j ]=min( f[ k-1 ] [ i ] [ j ]，f[ k-1 ] [ i ] [ k ]+f [ k-1 ] [ k ] [ j ] )
這樣壓掉一維就變成了我們熟悉的樣子
而這題發現這裡的k剛好很符合題中時間這一要求，即時間不超過k時的最短路，而題中給的詢問t又是有序的（無序也可以排序）
所以就每次就用這個點的時間去更新一遍所有點的最短路，即可達到題意的目的
判斷一下時間是否超過了，或者能否到達即可
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=205; const int maxm=100010; int n,m,q; int t[maxn],d[maxn][maxn],a[maxn][maxn]; void upd(int k) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[j][i]=d[i][k]+d[k][j]; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&t[i]); memset(d,0x3f,sizeof(d)); for(int i=0;i<n;i++)d[i][i]=0; for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); d[x][y]=d[y][x]=z; } scanf("%d",&q); int now=0;//用於記錄當前時間對應的編號，從第一個村莊開始 for(int i=1,x,y,z;i<=q;i++){ scanf("%d%d%d",&x,&y,&z); while(t[now]<=z && now<n){ upd(now);//依次更新點，使它可以被用來更新其他的點 now++; }//處理在它之前建立的村莊 if(t[x]>z || t[y]>z)printf("-1 "); else{ if(d[x][y]==0x3f3f3f3f)printf("-1 "); else printf("%d ",d[x][y]); } } }