L3-007. 天梯地图

题目链接：https://www.patest.cn/contests/gplt/L3-007
Dijstra
这题是Dijstra的变形，麻烦的是两种最短路的相同距离时的选择条件不同，也就是说要写两个Dijstra函数。很早就写完了代码，不过debug了一星期，最后还是参考他人博客才知道自己错哪了= =(易错点已注释)
代码如下：
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<stack>
  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<n;++i){
 24         lendis[i]=INF;
 25         timedis[i]=INF;
 26         for(int j=0;j<n;++j){
 27             lenmp[i][j]=INF;
 28             timemp[i][j]=INF;
 29         }
 30     }
 31     while(m--){
 32         int a,b,one,length,time;
 33         scanf("%d%d%d%d%d",&a,&b,&one,&length,&time);
 34         if(one){
 35             lenmp[a][b]=length;
 36             timemp[a][b]=time;
 37         }else{
 38             lenmp[a][b]=lenmp[b][a]=length;
 39             timemp[a][b]=timemp[b][a]=time;
 40         }
 41     }
 42     scanf("%d%d",&Start,&End);
 43     /**数据处理**/
 44     lenDijstra();
 45     timeDijstra();
 46     /**输出**/
 47     int k=End;
 48     bool flag=1;
 49     stack<int>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("
");
 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("
");
 72         printf("Distance = %d:",lendis[End]);
 73         printf("% d",Start);
 74         stack<int>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("
");
 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<n;++i){
 98             if(mark[i]&&Min>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<n;++i){
106             int d=lendis[index]+lenmp[index][i];
107             if(mark[i]&&lendis[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<node[i]){
112                 lenpre[i]=index;
113                 node[i]=node[index]+1;
114             }
115         }
116     }
117 }
118 void timeDijstra(){
119     memset(mark,1,sizeof(mark));
120     int dis[N];
121     for(int i=0;i<n;++i)
122         dis[i]=lenmp[Start][i];
123     timedis[Start]=0;
124     dis[Start]=0;
125     while(1){
126         int Min=INF,index;
127         for(int i=0;i<n;++i){
128             if(mark[i]&&Min>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<n;++i){
136             int t=timedis[index]+timemp[index][i];
137             int d=dis[index]+lenmp[index][i];
138             if(mark[i]&&timedis[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 }