PAT 1111 Online Map
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:
Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:
V1 V2 one-way length time
where V1 and V2 are the indices (from 0 to N−1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.
Finally a pair of source and destination is given.
Output Specification:
For each case, first print the shortest path from the source to the destination with distance D in the format:
Distance = D: source -> v1 -> ... -> destination
Then in the next line print the fastest path with total time T:
Time = T: source -> w1 -> ... -> destination
In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.
In case the shortest and the fastest paths are identical, print them in one line in the format:
Distance = D; Time = T: source -> u1 -> ... -> destination
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
分析
参考最短路径解析
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int maxium=99999999999;
int n, m;
vector<int> pre1(505, -1), pre2(505, -1), visited(505, 0), _time(505,0);
vector<int> cnt(505, maxium);
struct road{
int end;
int len;
int Time;
road(int e, int l, int t):end(e), len(l), Time(t){
}
};
int findmin(vector<int> &minset){
int min=maxium, temp=-1;
for(int i=0; i<n; i++)
if(minset[i]<=min&&visited[i]==0){
temp=i;
min=minset[i];
}
visited[temp]=1;
return temp;
}
int main(){
vector<int> mint(505,maxium), mind(505, maxium);
scanf("%d %d",&n, &m);
int s, e, l, t, o;
vector<vector<road>> map(n);
for(int i=0; i<m; i++){
scanf("%d %d %d %d %d", &s, &e, &o, &l, &t);
road r(e, l, t);
map[s].push_back(r);
if(o==0){
road r1(s, l, t);
map[e].push_back(r1);
}
}
int b, d;
scanf("%d %d",&b, &d);
mind[b]=0;
int num=n;
while(num--){
int t=findmin(mind);
for(int i=0; i<map[t].size(); i++){
road temp=map[t][i];
if(visited[temp.end]==1) continue;
if(mind[temp.end]>mind[t]+temp.len){
mind[temp.end]=mind[t]+temp.len;
pre1[temp.end]=t;
_time[temp.end]=_time[t]+temp.Time;
}else if(mind[temp.end]==mind[t]+temp.len&&_time[t]+temp.Time<_time[temp.end]){
_time[temp.end]=_time[t]+temp.Time;
pre1[temp.end]=t;
}
}
}
fill(visited.begin(), visited.end(), 0);
mint[b]=0;
cnt[b]=0;
num=n;
while(num--){
int t=findmin(mint);
for(int i=0; i<map[t].size(); i++){
road temp=map[t][i];
if(visited[temp.end]==1) continue;
if(mint[temp.end]>mint[t]+temp.Time){
mint[temp.end]=mint[t]+temp.Time;
pre2[temp.end]=t;
cnt[temp.end]=cnt[t]+1;
}else if(mint[temp.end]==mint[t]+temp.Time&&cnt[temp.end]>cnt[t]+1){
pre2[temp.end]=t;
cnt[temp.end]=cnt[t]+1;
}
}
}
vector<int> ans1, ans2;
int temp=e;
stack<int> st;
while(temp!=-1){
st.push(temp);
temp=pre1[temp];
}
while(st.size()!=0){
ans1.push_back(st.top());
st.pop();
}
temp=e;
while(temp!=-1){
st.push(temp);
temp=pre2[temp];
}
while(st.size()!=0){
ans2.push_back(st.top());
st.pop();
}
if(ans1!=ans2){
printf("Distance = %d: ", mind[e]);
for(int i=0; i<ans1.size(); i++) printf("%d%s", ans1[i], i!=(ans1.size()-1)?" -> ":"\n");
printf("Time = %d: ", mint[e]);
for(int i=0; i<ans2.size(); i++) printf("%d%s", ans2[i], i!=(ans2.size()-1)?" -> ":"\n");
}else{
printf("Distance = %d; Time = %d: ", mind[e], mint[e]);
for(int i=0; i<ans1.size(); i++) printf("%d%s", ans1[i], i!=(ans1.size()-1)?" -> ":"\n");
}
return 0;
}
最新文章
- Collection集合
- 2、实现不同子网之间的信息交流(互相可以PING通)
- linux常用命令 (mac ),积少成多
- 理解Java中的接口
- hdu 5273 Dylans loves sequence
- JDK + Tomcat 安装配置
- Landsat8数据不同波段组合的用途
- springmvc java.lang.NoSuchMethodError: com.fasterxml.jackson.core.JsonFactory.requiresPropertyOrdering()Z
- java多继承
- input表单提交完毕,返回重新填入有黄色背景,和 历史记录 清除
- Python-递归初识-50
- ios黑科技
- Log4J Appender - 将Log4J的日志内容发送到agent的source
- sitecore系统教程之内容创作入门
- 关于iOS设备的那些事
- 工作总结 vue 城会玩
- 关于一道JS面试题的思考
- JavaScript Big-Int
- Hexo博客部署codingNet静态资源无法加载
- Bandit:一种简单而强大的在线学习算法