[luogu]P1119 灾后重建 Floyd

前言

非常好的一个题 传送门 :

思路

这次唯一的限制就是 加边是在某个时间后才可以的

也就是 我们如果暴力的话 需要从每个时间开始 然后依次加边 这样子我们才可以过

但是算一下会t 正好1e9

考虑 floyd

floyd最外层的那个循环 k正好不就是

用前k个点更新嘛

又因为题目给出的是排序之后的数据

因为我们可以直接跑floyd

CODE

#include 
using namespace std;
const int N  = 210;
int n,m;
int f[N][N];
int t[N];


void solve()
{
 cin>>n>>m;
 for(int i = 0;i>t[i];
 
 memset(f,0x3f,sizeof f);

 for(int i = 0;i>a>>b>>c;
     f[a][b] =f[b][a] = c;
 }
 
 int q ;cin>>q;
 int now  = 0 ;
 while( q -- )
 {
     int a,b,c;
     cin>>a>>b>>c;
     
     while(t[now]