hdu 2962

    技术2022-05-11  18

         http://acm.hdu.edu.cn/showproblem.php?pid=2962  怪题..................................

    最短路径呀,一开始不知道怎么去平衡题意中的两个条件,后来看以人家的解题思路,才知道只要在2分查找它的最大高度,然后在最大高度的条件下,去求其最短路径,以前没怎么用过2分,今天居然用在最短路径中,感觉挺神奇的,呵呵.............

    #include<iostream>using namespace std;const int MAX=1001;const int MAXINT=999999999;int map[MAX][MAX][2];int visit[MAX];int dist[MAX];int path[MAX];int n,m,b,e,tall,fist,mid; bool Dijkstra(){     for(int i=1;i<=n;i++)     {             visit[i]=0;             if(map[b][i][0]>=mid)                  dist[i]=map[b][i][1];              else dist[i]=MAXINT;                 path[i]=b;     }     visit[b]=1;     int k=-1,min;      for(int i=1;i<n;i++)     {           min=MAXINT;            for(int j=1;j<=n;j++)                 if(!visit[j]&&min>dist[j]&&map[path[j]][j][0]>=mid)                 {                               min=dist[j];                               k=j;                  }             if(k!=-1) visit[k]=1;           else return false;           if(k==e) return true;                 for(int j=1;j<=n;j++)                 if(!visit[j]&&map[k][j][1]!=MAXINT&&map[k][j][0]>=mid)                      if(dist[j]>dist[k]+map[k][j][1])                      {                               dist[j]=dist[k]+map[k][j][1];                               path[j]=k;                      }      }         return false; }int main(){    int T=0;    scanf("%d%d",&n,&m);     while(1)    {    if(n==0&&m==0) break;     if(T>0) printf("/n");      printf("Case %d:/n",++T);    for(int i=1;i<=n;i++)    {            for(int j=1;j<=n;j++)                    map[i][j][1]=MAXINT;            map[i][i][1]=MAXINT;                                    }     int x,y,height,length;     for(int i=1;i<=m;i++)    {            scanf("%d%d%d%d",&x,&y,&height,&length);            map[x][y][1]=map[y][x][1]=length;            if(height==-1) height=MAXINT;            map[x][y][0]=map[y][x][0]=height;                               }    scanf("%d%d%d",&b,&e,&tall);    fist=1;    int ans;    mid=(fist+tall)/2;    while(fist<=tall)    {          if(Dijkstra())          {                  ans=dist[e];                  fist=mid+1;          }          else    tall=mid-1;       mid=(fist+tall)/2;        }    if(tall==0)  printf("cannot reach destination/n");   else    {    printf("maximum height = %d/n",tall);   printf("length of shortest route = %d/n",ans);  }        scanf("%d%d",&n,&m);  }    return 0;}

       


    最新回复(0)