灾后重建 Floyd-白红宇

灾后重建 Floyd

阅读量：6983 次

发布时间：2019-06-27

本文共 3654 字，大约阅读时间需要 12 分钟。

题目背景

题目描述

给出 $BBB地区的村庄数NNN，村庄编号从000到N−1N-1N−1，和所有MMM条公路的长度，公路是双向的。并给出第iii个村庄重建完成的时间tit_iti，你可以认为是同时开始重建并在第tit_iti天重建完成，并且在当天即可通车。若tit_iti为000则说明地震未对此地区造成损坏，一开始就可以通车。之后有QQQ个询问(x,y,t)(x, y, t)(x,y,t)，对于每个询问你要回答在第ttt天，从村庄xxx到村庄y的最短路径长度为多少。如果无法找到从xxx村庄到yyy村庄的路径，经过若干个已重建完成的村庄，或者村庄xxx或村庄yyy在第t天仍未重建完成，则需要返回−1-1−1。$

输入输出格式

输入格式：

第一行包含两个正整数

第二行包含 $NNN个非负整数t0,t1,…,tN−1t_0, t_1,…, t_{N-1}t0,t1,…,tN−1，表示了每个村庄重建完成的时间，数据保证了t0≤t1≤…≤tN−1t_0 ≤ t_1 ≤ … ≤ t_{N-1}t0≤t1≤…≤tN−1。$

接下来

接下来一行也就是

接下来

输出格式：

共

输入输出样例

输入样例#1：

4 51 2 3 40 2 12 3 13 1 22 1 40 3 542 0 20 1 20 1 30 1 4

输出样例#1：

-1-154

说明

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

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

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

对于 $100%100\%100%的数据，有N≤200N≤200N≤200，M≤N×(N−1)/2M≤N \times (N-1)/2M≤N×(N−1)/2，Q≤50000Q≤50000Q≤50000，所有输入数据涉及整数均不超过100000100000100000。$

$知识点不难，重要是idea;$

$由于保证 t 是严格递增的，那么我们每次更新就行了；$

$floyd;$

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       //#include
                       
                        //#pragma GCC optimize(2)using namespace std;#define maxn 200005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-4typedef pair
                        
                          pii;#define pi acos(-1.0)//const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                         
                           pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}int sqr(int x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int dis[300][300];int n, m;int fixt[maxn];void floyd(int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[j][i] = dis[i][k] + dis[k][j]; } }}int main() { //ios::sync_with_stdio(0); rdint(n); rdint(m); for (int i = 0; i < n; i++)rdint(fixt[i]); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++)dis[i][j] = dis[j][i] = 1e9; } for (int i = 0; i <= n; i++) { dis[i][i] = 0; } for (int i = 0; i < m; i++) { int u, v, w; rdint(u); rdint(v); rdint(w); dis[u][v] = dis[v][u] = w; } int cur = 0; int q; cin >> q; while (q--) { int x, y, t; rdint(x); rdint(y); rdint(t); while (cur < n&&fixt[cur] <= t) { floyd(cur); cur++; } if (fixt[x] > t || fixt[y] > t) { cout << -1 << endl; } else { if (dis[x][y] == 1e9)cout << -1 << endl; else cout << dis[x][y] << endl; } } return 0;}

转载于:https://www.cnblogs.com/zxyqzy/p/10284451.html

你可能感兴趣的文章