本文共 1868 字,大约阅读时间需要 6 分钟。
题目:
本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查询请求,地图上都至少存在一条可达路线。 输入格式: 输入在第一行给出两个正整数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 150 1 0 1 18 0 0 1 14 8 1 1 15 4 0 2 35 9 1 1 40 6 0 1 17 3 1 1 28 3 1 1 22 5 0 2 22 1 1 1 11 5 0 1 31 4 0 1 19 7 1 1 33 1 0 2 56 3 1 2 15 3
输出样例1:
Time = 6: 5 => 4 => 8 => 3Distance = 3: 5 => 1 => 3
输入样例2:
7 90 4 1 1 11 6 1 3 12 6 1 1 12 5 1 2 23 0 0 1 13 1 1 3 13 2 1 2 14 5 0 2 26 5 1 2 13 5
输出样例2:
Time = 3; Distance = 4: 3 => 2 => 5
#includeusing namespace std;const int MAX=0x3f3f3f3f;const int maxn=505;int n,m,s,d;struct ROAD{ bool one_way; int length; int time;} road[maxn][maxn];struct NODE{ int time_pre; int length_pre; int nodenum; bool vis; int dist;} node[maxn];bool judge(int a[],int b[],int x,int y){ if(x==y) { for(int i=0; i >n>>m; int v1,v2,one_way,length,time; for(int i=0; i >s>>d;}void Dijkstra_time(){ for(int i=0; i =0; i--) { cout<<' '< "; } } else { printf("Time = %d:",road[s][d].time); for(int i=x-1; i>=0; i--) { cout<<' '< "; } cout< =0; i--) { cout<<' '< "; } }}int main(){ //freopen("in.txt","r",stdin); init(); Dijkstra_length(); Dijkstra_time(); solve();}
更多PTA代码请到我的博客里参考
ps:代码仅供参考,请勿抄袭
转载地址:http://nmqbi.baihongyu.com/