思路：这道题看n的范围很小（n<=200)，显然就用floyd可以解决的问题，但又并不是简单的floyd算法，还是需要一些小小的变化。一开始我的思路是先跑一次弗洛伊德最短路，这样子显然复杂度很高，并且题目中的路径长度是时刻可能更新的，所以我们应该在修建的时候再跑最短路。可以用一个变量来记录修改的点，这样子就可以大幅度的优化。

代码如下

#include
     
      using namespace std;const int maxn=1010;const int N=250;int n,m,x,y,v,T;int t[maxn];int f[N][N];int flag[N][N];int xx,yy,tt;int start;//动态变化的那个点int main(){    scanf("%d%d",&n,&m);    for(int i=0;i
      
       tt||t[yy]>tt)        {            printf("-1\n");        }        else        {            printf("%d\n",f[xx][yy]);        }    }    return 0;}
      
     

等等，但这样似乎只有30分，吸氧50 ，T了7个点

究其原因，是因为每次跑弗洛伊德的时候，start都是又从零开始枚举的，这样显然是没有必要的

所以我们就将他简单改一下

 

#include
     
      using namespace std;const int maxn=1010;const int N=250;int n,m,x,y,v,T;int t[maxn];int f[N][N];int flag[N][N];int xx,yy,tt;int start;int Read(){    int X = 0 ; char ch = getchar() ;    while(ch > '9' || ch < '0') ch = getchar() ;    while(ch >= '0' && ch <= '9')    X = (X << 1) + (X << 3) + (ch ^ 48), ch = getchar() ;    return X ;}int main(){    n=Read(),m=Read();    for(int i=0;i
      
       tt||t[yy]>tt)        {            printf("-1\n");        }        else        {            printf("%d\n",f[xx][yy]);        }    }    return 0;}
      
     

 

因为修建的时候那个点都是一遍更新的，并且时间是单调递增的

所以只需要更新一遍就得了，那个动态的点就不用再次清零了。