P1119 灾后重建(floyd)

题目背景

B 地震后，所有村庄都造成了一定的损坏，但地震对公路没有影响。但在村庄重建之前，所有未重建的村庄的道路都不能通车。换句话说，只有连接两个重建村庄的道路才能通车，只能到达重建村庄。

题目描述

给出 B 该地区的村庄数量NN，村庄编号从0到N?1，和所有M公路长度为双向。并给出第i村庄重建完成的时间ti，你可以认为它是同时重建的ti天重建完成，当天即可通车。若ti为0说明地震没有损坏这个地区，一开始就可以通车。之后有Q个询问(x,y,t)(x,y,t)，你必须回答每一个问题。t天，从村庄x到村庄y最短路径长度是多少？若找不到从x村庄到y村庄的路径经过几个重建的村庄或村庄x或村庄y在第t天还没有重建，需要返回-1。

输入格式

第一行包括两个正整数N,MN,M，表示村庄和公路的数量。

第二行包含NN个非负整数t_0, t_1,…, t_{N-1}t0,t1,…,tN?1.表示每个村庄重建的时间，数据得到保证t_0 ≤ t_1 ≤ … ≤ t_{N-1}t0≤t1≤…≤tN?1。

接下来MM每行33个非负整数i, j, wi,j,w，ww对于不超过100010000的正整数，表示有一个连接村庄ii与村庄jj长度为ww，保证i≠ji=j，任何一对村庄只有一条路。

下一行就是M 3M 三行包含正整数QQ，表示QQ个询问。

接下来QQ每行33个非负整数x, y, tx,y,t，询问在第tt天，从村庄xx到村庄yy数据保证了最短路径的长度tt不下降。

输出格式

共QQ好吧，每一个问题(x, y, t)(x,y,t)输出相应的答案，即在第一位tt天，从村庄xx到村庄yy最短路径的长度是多少？如果在第二天找不到从xx村庄到yy村庄的路径经过几个已经重建的村庄，或者x或村庄yy在第tt天还没修好，输出-1?1。

输入输出样例

输入 #1复制

4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4

输出 #1复制

-1 -1 5 4

说明/提示

对于30\0%的数据，N≤50N≤50；

对于30\0%的数据，t_i= 0ti=0，其中有20\ %的数据有t_i = 0ti=0且N>50N>50；

对于50\P%数据，有Q≤100Q≤100；

对于100\0%的数据，有N≤200N≤200，M≤N \times (N-1)/2M≤N×(N?1)/2，Q≤50000Q≤所有输入数据涉及的总数不超过1万万。

多源汇最短路问题

如果只会floyd模板这个问题做不到，

for(int k=1;k<=n;k  )     for(int i=1;i<=n;i  )         for(int j=1;j<=n;j  )             dist[i][j]=min(dist[i][j],dist[i][k] dist[k][j]);

用前k点更新更新过程i，j两点之间的距离，这个问题是否可以通过村庄的时间限制和随时增加

故将floyd()变成这样:

void floyd(int k) {     for(int i=1;i<=n;i  )         for(int j=1;j<=n;j  )             dist[i][j]=min(dist[i][k] dist[k][j],dist[i][j]); }

因为询问给出的t增加，所以输入时更新；

代码：

#include  #include  using namespace std; int g[210][210],a[210]; const int inf=0x3f3f3f3f; int n,m,t; void floyd(int k) {         for(int i=1;i<=n;i  )             for(int j=1;j<=n;j  )                 g[i][j]=min(g[i][j],g[i][k] g[k][j]); } int main() {     int u,v,w;     cin>>n>>m;     for(int i=1;i<=n;i  ){         for(int j=1;j<=n;j  )             if(i==j) g[i][j]=0;             else g[i][j]=inf;     }     for(int i=1;i<=n;i  ) scanf("%d",&a[i]);     while(m--){         scanf("%d%d%d",&u,&v,&w);         u  ,v  ;         g[u][v]=g[v][u]=w;     }     cin>>t;     int cur=1;     while(t--)     {         scanf("%d%d%d",&u,&v,&w);         u  ,v  ;         while(a[cur]<=w&&cur<=n) {floyd(cur);cur  ;}    //边输入边更新         if(a[u]>w||a[v]>w||g[u][v]==inf) printf("-1\n");         else printf("%d\n",g[u][v]);     }     return 0; }