L3-007. 天梯地图

题目链接：

Dijstra

这题是Dijstra的变形，麻烦的是两种最短路的相同距离时的选择条件不同，也就是说要写两个Dijstra函数。很早就写完了代码，不过debug了一星期，最后还是参考他人博客才知道自己错哪了= =(易错点已注释)

代码如下：

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N 505  5 using namespace std;  6 const int INF=0x3f3f3f3f;  7 bool mark[N];  8 int n,Start,End;  9 int lenmp[N][N]; 10 int timemp[N][N]; 11 int lendis[N]; 12 int timedis[N]; 13 int lenpre[N]; 14 int timepre[N]; 15 void lenDijstra(); 16 void timeDijstra(); 17 int main(void){ 18     /**输入**/ 19     memset(lenpre,-1,sizeof(lenpre)); 20     memset(timepre,-1,sizeof(timepre)); 21     int m; 22     scanf("%d%d",&n,&m); 23     for(int i=0;i
        

times; 50 while(k!=Start){ 51 times.push(k); 52 if(timepre[k]!=lenpre[k])flag=0; 53 k=timepre[k]; 54 } 55 if(flag){ 56 printf("Time = %d;",timedis[End]); 57 printf(" Distance = %d:",lendis[End]); 58 printf("% d",Start); 59 while(!times.empty()){ 60 printf(" => %d",times.top()); 61 times.pop(); 62 } 63 printf("\n"); 64 }else{ 65 printf("Time = %d:",timedis[End]); 66 printf("% d",Start); 67 while(!times.empty()){ 68 printf(" => %d",times.top()); 69 times.pop(); 70 } 71 printf("\n"); 72 printf("Distance = %d:",lendis[End]); 73 printf("% d",Start); 74 stack

diss; 75 k=End; 76 while(k!=Start){ 77 diss.push(k); 78 k=lenpre[k]; 79 } 80 while(!diss.empty()){ 81 printf(" => %d",diss.top()); 82 diss.pop(); 83 } 84 printf("\n"); 85 } 86 return 0; 87 } 88 void lenDijstra(){ 89 int node[N]; 90 memset(node,0,sizeof(node)); 91 node[Start]=1; 92 93 memset(mark,1,sizeof(mark)); 94 lendis[Start]=0; 95 while(1){ 96 int Min=INF,index; 97 for(int i=0;i

lendis[i]){ 99 Min=lendis[i];100 index=i;101 }102 }103 if(Min==INF)break;104 mark[index]=0;105 for(int i=0;i

d){108 lendis[i]=d;109 lenpre[i]=index;110 node[i]=node[index]+1; /*非node[i]++*/111 }else if(mark[i]&&lendis[i]==d&&node[index]+1

timedis[i]){129 Min=timedis[i];130 index=i;131 }132 }133 if(Min==INF)break;134 mark[index]=0;135 for(int i=0;i

t){139 dis[i]=d;140 timedis[i]=t;141 timepre[i]=index;142 }else if(mark[i]&&timedis[i]==t&&dis[i]>d){143 dis[i]=d;144 timepre[i]=index;145 }146 }147 }148 }