problem
L3-007 天梯地图 (30分) 本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。
输入格式： 输入在第一行给出两个正整数N（2 ≤ N ≤ 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：
V1 V2 one-way length time 其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。
输出格式： 首先按下列格式输出最快到达的时间T和用节点编号表示的路线：
Time = T: 起点 => 节点1 => … => 终点 然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：
Distance = D: 起点 => 节点1 => … => 终点 如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
如果这两条路线是完全一样的，则按下列格式输出：
Time = T; Distance = D: 起点 => 节点1 => … => 终点 输入样例1： 10 15 0 1 0 1 1 8 0 0 1 1 4 8 1 1 1 5 4 0 2 3 5 9 1 1 4 0 6 0 1 1 7 3 1 1 2 8 3 1 1 2 2 5 0 2 2 2 1 1 1 1 1 5 0 1 3 1 4 0 1 1 9 7 1 1 3 3 1 0 2 5 6 3 1 2 1 5 3 输出样例1： Time = 6: 5 => 4 => 8 => 3 Distance = 3: 5 => 1 => 3 输入样例2： 7 9 0 4 1 1 1 1 6 1 3 1 2 6 1 1 1 2 5 1 2 2 3 0 0 1 1 3 1 1 3 1 3 2 1 2 1 4 5 0 2 2 6 5 1 2 1 3 5 输出样例2： Time = 3; Distance = 4: 3 => 2 => 5
n个点m条边的有向图，求两次最短路，打印路径如果最快到达路线不唯一，则输出几条最快路线中最短的那条如果最短距离的路线不唯一，则输出途径节点数最少的那条
solution
Dijkstra+路径打印（邻接表），这不是个模板么，，看我秒他。。WA2,4，这也能错？改不动了改不动了。。。找不到数据，只好重新写一个，这次把dij拆出来，路径打印换成递归（大家都这样）结果WA2原来的那个改出来了，，数据点2,4的错误地方在注释里注明了
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 550;
int n
, m
, s
, t
;
int e
[2][maxn
][maxn
], dist
[2][maxn
], vis
[2][maxn
], pre
[2][maxn
], w
[2][maxn
];
void Dijkstra(int rk
){
memset(dist
[rk
],0x3f,sizeof(dist
[rk
]));
memset(vis
[rk
],0,sizeof(vis
[rk
]));
memset(pre
[rk
],-1,sizeof(pre
[rk
]));
dist
[rk
][s
] = 0;
for(int i
= 0; i
< n
; i
++){
int u
= -1, _min
= 1e9;
for(int j
= 0; j
< n
; j
++){
if(!vis
[rk
][j
] && dist
[rk
][j
]<_min
){
_min
= dist
[rk
][j
]; u
= j
;
}
}
if(u
==-1)return ;
vis
[rk
][u
] = 1;
for(int j
= 0; j
< n
; j
++){
if(!vis
[rk
][j
] && dist
[rk
][j
]>dist
[rk
][u
]+e
[rk
][u
][j
]){
dist
[rk
][j
] = dist
[rk
][u
]+e
[rk
][u
][j
];
pre
[rk
][j
] = u
;
if(rk
==0){
w
[rk
][j
] = w
[rk
][u
]+1;
}
if(rk
==1){
w
[rk
][j
] = w
[rk
][u
]+e
[!rk
][u
][j
];
}
}else if(!vis
[rk
][j
] && dist
[rk
][j
] == dist
[rk
][u
]+e
[rk
][u
][j
]){
if(rk
==0){
if(w
[rk
][j
] > w
[rk
][u
]+1){
w
[rk
][j
] = w
[rk
][u
]+1;
pre
[rk
][j
] = u
;
}
}
if(rk
==1){
if(w
[rk
][j
] > w
[rk
][u
]+e
[!rk
][u
][j
]){
w
[rk
][j
] = w
[rk
][u
]+e
[!rk
][u
][j
];
pre
[rk
][j
] = u
;
}
}
}
}
}
}
void Print(int rk
, int x
){
if(x
==-1){
return ;
}else{
Print(rk
, pre
[rk
][x
]);
printf(" %d =>", x
);
}
}
int main(){
memset(e
,0x3f,sizeof(e
));
cin
>>n
>>m
;
for(int i
= 1; i
<= m
; i
++){
int a
, b
, on
, le
, ti
;
cin
>>a
>>b
>>on
>>le
>>ti
;
if(on
==1){
e
[0][a
][b
] = le
;
e
[1][a
][b
] = ti
;
}else{
e
[0][a
][b
] = le
;
e
[1][a
][b
] = ti
;
e
[0][b
][a
] = le
;
e
[1][b
][a
] = ti
;
}
}
cin
>>s
>>t
;
Dijkstra(0);
Dijkstra(1);
int ok
= 1, i
= pre
[0][t
], j
= pre
[1][t
];
while(i
!=-1 && j
!=-1){
if(pre
[0][i
] != pre
[0][j
]){ok
=0;break;}
i
= pre
[0][i
];
j
= pre
[1][j
];
}
if(ok
){
printf("Time = %d;",dist
[1][t
]);
printf(" Distance = %d:",dist
[0][t
]);
Print(1,pre
[1][t
]);
printf(" %d\n",t
);
return 0;
}
printf("Time = %d:",dist
[1][t
]);
Print(1,pre
[1][t
]);
printf(" %d\n",t
);
printf("Distance = %d:",dist
[0][t
]);
Print(0,pre
[0][t
]);
printf(" %d",t
);
return 0;
}
