hdu 1690 构图后Floyd 数据很大-白红宇

hdu 1690 构图后Floyd 数据很大

阅读量：5266 次

发布时间：2019-06-14

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

WA了好多次... 这题要用long long 而且INF要设大一点

Sample Input

2 //T

1 2 3 4 1 3 5 7 //L1-L4 C1-C4 距离和花费

4 2 //结点数询问次数

1 //结点的横坐标

1 4 //起点终点

4 1

1 2 3 4 1 3 5 7

4 1

1 4

Sample Output

Case 1:

The minimum cost between station 1 and station 4 is 3.

The minimum cost between station 4 and station 1 is 3.

Case 2:

Station 1 and station 4 are not attainable.

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 # include 
          
            6 # include 
           
             7 # define LL long long 8 using namespace std ; 9 10 const LL INF=0x7f7f7f7f7f7f7f7fLL;11 const int MAXN=210;12 13 LL L[10] ;14 LL C[10] ;15 LL x[MAXN] ;16 17 LL dis[MAXN][MAXN];18 int n ;19 20 21 void floyed()//节点从1~n编号22 {23 int i,j,k;24 for(k=1;k<=n;k++)25 for(i=1;i<=n;i++)26 for(j=1;j<=n;j++)27 if(dis[i][k]+dis[k][j] < dis[i][j] && dis[i][k] != INF && dis[k][j] != INF)28 dis[i][j]=dis[i][k]+dis[k][j];29 30 }31 32 LL Cost(LL d)33 {34 if (d < 0)35 d *= -1 ;36 if (d > 0 && d<= L[1])37 return C[1] ;38 if (d > L[1] && d<= L[2])39 return C[2] ;40 if (d > L[2] && d<= L[3])41 return C[3] ;42 if (d > L[3] && d<= L[4])43 return C[4] ;44 return INF ;45 }46 47 int main ()48 {49 // freopen("in.txt","r",stdin) ;50 int cnt ;51 int T ;52 cin>>T ;53 int Case = 0 ;54 while (T--)55 {56 Case++ ;57 cout<<"Case "<
            
             <<":"<
             
              >L[i];62 for (i = 1 ; i <= 4 ; i++)63 cin>>C[i];64 65 cin>>n>>cnt ;66 for (i = 1 ; i <= n ; i++)67 cin>>x[i];68 for (i = 1 ; i <= n ; i++)69 for (j = 1 ; j <= n ; j++)70 {71 if(i==j)dis[i][j]=0;72 else dis[i][j]=INF;73 }74 for (i = 1 ; i <= n ; i++)75 for (j = i+1 ; j <= n ; j++)76 {77 LL d = x[i] - x[j] ;78 w = Cost(d) ;79 dis[i][j] = w ;80 dis[j][i] = w ;81 }82 floyed() ;83 int u , v ;84 while(cnt--)85 {86 cin>>u>>v ;87 if (dis[u][v] != INF)88 cout<<"The minimum cost between station "<
              <<" and station "<
               
                <<" is "<
                
                 <<"."<