TTTTTTTTTTTTTTTTT CF #182 div1 B floyd-白红宇

TTTTTTTTTTTTTTTTT CF #182 div1 B floyd

阅读量：4919 次

发布时间：2019-06-11

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

有 n(3≤n≤100) 个站点，当第一次到达站点 u 的时候会增加寿命 a_u(1≤a_u≤10³)，题目给了 n 个站点的二位空间坐标，每两个站点之间的距离为曼哈顿距离（dis(i, j)=|x_i-x_j|+|y_i-y_j|），从站点 i 到达站点 j 需要的时间为 dis(i, j)*d（d 是题目给定的一个常数，且 10³≤d≤10⁵）。某个人最开始的时候在站点 1，他想到站点 n 去，问，他最开始至少剩下多少寿命才能活着到达站点 n？

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;typedef long long ll;typedef unsigned long long Ull;#define MM(a,b) memset(a,b,sizeof(a));const double eps = 1e-10;const int inf = 0x3f3f3f3f;const double pi=acos(-1);const int mod=100000000;ll max(ll a,ll b){return a>b?a:b;};ll min(ll a,ll b){return a

　分析：n才200，显然暗示了n^3的算法，当然floyd

转载于:https://www.cnblogs.com/smilesundream/p/5383251.html

你可能感兴趣的文章