The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

7.25航电练习赛 F题 trucking 解题报告(二分+Dij)

这道题实际上就是最短路,只不过增加了高度这个限制条件,由于时间限制是10s,我们不妨二分枚举出所有高度在1-limit之间的情况(时间复杂度是n^2log n,可以接受)取最大的即可。
PS:本人觉得此题最BT之处在于输出格式,Fuck!最后一个Case居然不要空行,害我PE十几次。

#include<iostream>
#include
<cmath>
#include
<cstdio>
#include
<algorithm>
using namespace std;
#define MAX 1001
#define MAX_INTEGER  0x7fffffff


int n,m;
int graph[MAX][MAX];
int copygraph[MAX][MAX];
int graphheight[MAX][MAX];
bool visit[MAX];
int dis[MAX];
int s,t,lim;
int maxn;
int shortestpath;
int casenum;

bool dijkstra(int s,int t,int graph[MAX][MAX])
{
    memset(visit,
false,sizeof(visit));
    
int i;
    
int j;
    
    
    
for(i=1;i<=n;i++)
    
{
        dis[i]
=graph[s][i];
    }

    graph[s][s]
=0;
    
    dis[s]
=0;
    visit[s]
=true;
    
for(i=1;i<n;i++)
    
{
        
int mark_num=n;
        
int mark_dis=MAX_INTEGER;
        
int temp=MAX_INTEGER;
        
for(j=1;j<=n;j++)
        
{
            
if(!visit[j]&&dis[j]<temp)
            
{
                mark_num
=j;
                temp
=dis[j];
                
            }

        }

        
if(temp==MAX_INTEGER)
            
return false;
        visit[mark_num]
=true;
        
if(mark_num==t)
            
return true;
        
for(j=1;j<=n;j++)
        
{
            
if((!visit[j])&&(graph[mark_num][j]<MAX_INTEGER))
            
{
                
int newdis=dis[mark_num]+graph[mark_num][j];
                
if(newdis<dis[j])
                
{
                    dis[j]
=newdis;
                }

            }

        }

    }

    
return false;
    
}


int main ()
{
//    FILE *in,*out;
//    in = fopen("trucking.in", "r");
//    out = fopen("out.txt","w");
      

    
int i,j;
    casenum
=0;
    
while(scanf("%d%d",&n,&m))

    
{
        casenum
++;
        maxn
=0;
        
if(n==0&&m==0)
            
break;
        
for(i=1;i<=n;i++)
        
{
            
for(j=1;j<=n;j++)
            
{
                
if(i==j)
                    graph[i][j]
=0;
                
else    
                    graph[i][j]
=MAX_INTEGER;
            }

        }

        
for(i=1;i<=m;i++)
        
{
            
int a,b,height,len;
            scanf(
"%d%d%d%d",&a,&b,&height,&len);
            graph[a][b]
=len;
            graph[b][a]
=len;
            
if(height==-1)

            
{
                graphheight[a][b]
=9999999;
                graphheight[b][a]
=9999999;
            }

            
else
            
{
                graphheight[a][b]
=height;
                graphheight[b][a]
=height;
            }


        
        }

        scanf(
"%d%d%d",&s,&t,&lim);
        
int l=1;
        
int r=lim;
        
while(l<=r)
        
{

            
int mid=(r+l)>>1;
            
for(i=1;i<=n;i++)
            
{

                
for(j=1;j<=n;j++)
                
{
                    copygraph[i][j]
=graph[i][j];

                    
if(graphheight[i][j]<mid&&i!=j)
                        copygraph[i][j]
=MAX_INTEGER;
                }

            }

            
if(dijkstra(s,t,copygraph)==false)
            
{
                r
=--mid;
                
continue;
            }

            
else
            
{

                l
=mid+1;
                maxn
=mid;
                shortestpath
=dis[t];
                
continue;
            }

        }

        
if(casenum>1)
            printf(
"\n");
        
if(maxn==0)
            printf(
"Case %d:\ncannot reach destination\n",casenum);
        
else
            printf(
"Case %d:\nmaximum height = %d\nlength of shortest route = %d\n",casenum,maxn,shortestpath);
    }

    
return 0;
}

posted on 2009-07-26 04:21 abilitytao 阅读(1007) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理