一、题目描述
原题链接 Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.
Input Specification:
Output Specification:
Sample Input 1:
10 15 0 1 0 1 1 8 0 0 1 1 4 8 1 1 1 3 4 0 3 2 3 9 1 4 1 0 6 0 1 1 7 5 1 2 1 8 5 1 2 1 2 3 0 2 2 2 1 1 1 1 1 3 0 3 1 1 4 0 1 1 9 7 1 3 1 5 1 0 5 2 6 5 1 1 2 3 5
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5 Time = 3: 3 -> 1 -> 5
Sample Input 2:
7 9 0 4 1 1 1 1 6 1 1 3 2 6 1 1 1 2 5 1 2 2 3 0 0 1 1 3 1 1 1 3 3 2 1 1 2 4 5 0 2 2 6 5 1 1 2 3 5
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5
二、解题思路
这道题不难但是有点复杂，利用了两次DIjkstra算法，还有就是利用pre数组和dfs还原路径。代码很长但是比较易懂，具体细节可参考注释。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std
;
const int INF
= 999999999;
const int maxn
= 510;
int dis
[maxn
], Time
[maxn
], e
[maxn
][maxn
], w
[maxn
][maxn
], dispre
[maxn
], Timepre
[maxn
], weight
[maxn
], nodeNum
[maxn
];
bool vis
[maxn
];
vector
<int> dispath
, Timepath
, temppath
;
int st
, fin
, minnode
= INF
;
void dfsdispath(int v
)
{
dispath
.push_back(v
);
if(v
== st
) return;
dfsdispath(dispre
[v
]);
}
void dfsTimepath(int v
)
{
Timepath
.push_back(v
);
if(v
== st
) return;
dfsTimepath(Timepre
[v
]);
}
int main()
{
fill(dis
, dis
+maxn
, INF
);
fill(Time
, Time
+maxn
, INF
);
fill(weight
, weight
+maxn
, INF
);
fill(e
[0], e
[0]+maxn
*maxn
, INF
);
fill(w
[0], w
[0]+maxn
*maxn
, INF
);
int n
, m
;
scanf("%d%d", &n
, &m
);
int a
, b
, flag
, len
, t
;
for(int i
=0; i
<m
; i
++)
{
scanf("%d%d%d%d%d", &a
, &b
, &flag
, &len
, &t
);
e
[a
][b
] = len
;
w
[a
][b
] = t
;
if(flag
!= 1)
{
e
[b
][a
] = len
;
w
[b
][a
] = t
;
}
}
scanf("%d%d", &st
, &fin
);
dis
[st
] = 0;
for(int i
=0; i
<n
; i
++) dispre
[i
] = i
;
for(int i
=0; i
<n
; i
++)
{
int u
= -1, minn
= INF
;
for(int j
=0; j
<n
; j
++)
{
if(!vis
[j
] && dis
[j
] < minn
)
{
u
= j
;
minn
= dis
[j
];
}
}
if(u
== -1) break;
vis
[u
] = true;
for(int v
=0; v
<n
; v
++)
{
if(!vis
[v
] && e
[u
][v
] != INF
)
{
if(e
[u
][v
] + dis
[u
] < dis
[v
])
{
dis
[v
] = e
[u
][v
] + dis
[u
];
dispre
[v
] = u
;
weight
[v
] = weight
[u
] + w
[u
][v
];
}
else if(e
[u
][v
] + dis
[u
] == dis
[v
] && weight
[u
] + w
[u
][v
] < weight
[v
])
{
weight
[v
] = weight
[u
] + w
[u
][v
];
dispre
[v
] = u
;
}
}
}
}
dfsdispath(fin
);
Time
[st
] = 0;
fill(vis
, vis
+maxn
, false);
for(int i
=0; i
<n
; i
++)
{
int u
= -1, minn
= INF
;
for(int j
=0; j
<n
; j
++)
{
if(!vis
[j
] && Time
[j
] < minn
)
{
u
= j
;
minn
= Time
[j
];
}
}
if(u
== -1) break;
vis
[u
] = true;
for(int v
=0; v
<n
; v
++)
{
if(!vis
[v
] && w
[u
][v
] != INF
)
{
if(w
[u
][v
] + Time
[u
] < Time
[v
])
{
Time
[v
] = Time
[u
] + w
[u
][v
];
Timepre
[v
] = u
;
nodeNum
[v
] = nodeNum
[u
] + 1;
}
else if(Time
[u
] + w
[u
][v
] == Time
[v
] && nodeNum
[u
]+1 < nodeNum
[v
])
{
Timepre
[v
] = u
;
nodeNum
[v
] = nodeNum
[u
] + 1;
}
}
}
}
dfsTimepath(fin
);
printf("Distance = %d", dis
[fin
]);
if(dispath
== Timepath
) printf("; Time = %d: ", Time
[fin
]);
else
{
printf(": ");
for(int i
=dispath
.size()-1; i
>=0; i
--)
{
printf("%d", dispath
[i
]);
if(i
!=0) printf(" -> ");
}
printf("\nTime = %d: ", Time
[fin
]);
}
for(int i
=Timepath
.size() - 1; i
>=0; i
--)
{
printf("%d", Timepath
[i
]);
if(i
!=0) printf(" -> ");
}
return 0;
}
