# PAT 1111. Online Map (30)

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,

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

``````  int t=prev[i];
ans=get_path(prev,i);
prev[i]=v1;
auto tt=get_path(prev,i);
if(f2(tt)<f2(ans))
ans=tt;
else
prev[i]=t;``````

``````#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <assert.h>
#include <memory.h>
#include <map>
#include <stack>
using namespace std;
#define INT_MAX       2147483647
#define repeat(n) for(int _i=0;_i<n;_i  )
typedef long long ll;
int N,M;
#define INPUT cin>>N>>M
#define get_v1(v) (v/500)
#define get_v2(v) (v%500)
int len[501][501]={0},u_time[501][501]={0};
int dist1[501];
int src,dst;
typedef vector<int> path;
int cal_time(const path& p)
{
int s=0;
for(int i=1;i<p.size();i  )
s =u_time[p[i-1]][p[i]];
return s;
}
int cal_path(const path& p)
{
int s=0;
for(int i=1;i<p.size();i  )
s =len[p[i-1]][p[i]];
return s;
}
path get_path(int *prev,int s)
{
path r;r.push_back(s);
while(prev[s]!=-1)
{
r.push_back(prev[s]);
s=prev[s];
}
return r;
}
int cal_intersections(const path& p){return p.size();}
void print_path(const path& p)
{
for(int i=p.size()-1;i>0;i--)
printf("%d -> ",p[i]);
cout<<p[0]<<endl;
}
typedef int (* fun)(const path& );
path find_path(int* dist,int len[][501],fun f1,fun f2)
{
dist[src]=0;
int visited[501]={0};
int prev[501]={0};
memset(prev,-1,501*4);
path ans;
while(1)
{
int v1=-1;
for(int i=0;i<N;i  )
if(!visited[i]){
if(v1==-1) v1=i; else
if(dist[i]<dist[v1])
v1=i;
}
//find min v1
visited[v1]=1;
if(v1==dst)
{
return get_path(prev,dst);
}
if(dist[v1]>dist[dst])
assert(0);
for(int i=0;i<N;i  )
{
if(dist[i]>dist[v1] len[v1][i]){
dist[i]=dist[v1] len[v1][i];
prev[i]=v1;
}else if(dist[i]==dist[v1] len[v1][i])
{
int t=prev[i];
ans=get_path(prev,i);
prev[i]=v1;
auto tt=get_path(prev,i);
if(f2(tt)<f2(ans))
ans=tt;
else
prev[i]=t;
}
}
}
return ans;
}
int use_time[501];
int main()
{
#ifdef _DEBUG
fstream cin("input.txt");
#endif
(INPUT);
for(int i=0;i<M;i  )
{
int v1,v2,one,l,t;
cin>>v1>>v2>>one>>l>>t;
if(!one)
len[v1][v2]=len[v2][v1]=l;
u_time[v1][v2]=u_time[v2][v1]=t;
assert(v1<N&&v2<N);
}
cin>>src>>dst;
assert(N<501);
//end input
for(int i=0;i<N;i  ) dist1[i]=INT_MAX;
const auto & p1=find_path(dist1,len,&cal_path,&cal_time);
for(int i=0;i<N;i  ) dist1[i]=INT_MAX;
const auto & p2=find_path(dist1,u_time,&cal_time,&cal_intersections );
if(p1==p2)
{
printf("Distance = %d; Time = %d: ",cal_path(p1),cal_time(p1));
print_path(p1);
}
else{
printf("Distance = %d: ",cal_path(p1));
print_path(p1);
printf("Time = %d: ",cal_time(p2));
print_path(p2);
}
return 0;
}``````

``````#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <assert.h>
#include <map>
#include <stack>
using namespace std;
#define INT_MAX       2147483647
#define repeat(n) for(int _i=0;_i<n;_i  )
typedef long long ll;
int N,M;
#define INPUT cin>>N>>M
#define get_v1(v) (v/500)
#define get_v2(v) (v%500)
int len[501][501]={0},u_time[501][501]={0};
int dist1[501];
int src,dst;
typedef vector<int> path;
int cal_time(const path& p)
{
int s=0;
for(int i=1;i<p.size();i  )
s =u_time[p[i-1]][p[i]];
return s;
}
int cal_path(const path& p)
{
int s=0;
for(int i=1;i<p.size();i  )
s =len[p[i-1]][p[i]];
return s;
}
int cal_intersections(const path& p){return p.size();}
void print_path(const path& p)
{
for(int i=0;i<p.size()-1;i  )
printf("%d -> ",p[i]);
cout<<p[p.size()-1]<<endl;
}
typedef int (* fun)(const path& );
path find_path(int* dist,int len[][501],fun f1,fun f2)
{
auto f=[&f1,&f2](const path& v1,const path& v2)->bool
{
int l1=f1(v1),l2=f1(v2);
if(l1==l2)
return f2(v1)<f2(v2);
return l1<l2;
};
set<path,decltype(f)> search(f);
dist[src]=0;
int visited[501]={0};
int min_len=INT_MAX;
path ans(1,src);
search.insert(ans);
while(!search.empty())
{
const auto p1=*search.begin();
int v1=*p1.rbegin();
visited[v1]=1;
search.erase(search.begin());
if(v1==dst)
{
return p1;
}
if(dist[v1]>dist[dst])
break;
for(int i=0;i<N;i  )
{
dist[i]=dist[v1] len[v1][i];
auto t=p1;
t.push_back(i);
search.insert(t);
}
}
while(1) dist;
assert(0);
return ans;
}
int use_time[501];
int main()
{
#ifdef _DEBUG
fstream cin("input.txt");
#endif
(INPUT);
for(int i=0;i<M;i  )
{
int v1,v2,one,l,t;
cin>>v1>>v2>>one>>l>>t;
if(!one)
len[v1][v2]=len[v2][v1]=l;
u_time[v1][v2]=u_time[v2][v1]=t;
assert(v1<N&&v2<N);
}
cin>>src>>dst;
assert(N<501);
//end input
for(int i=0;i<N;i  ) dist1[i]=INT_MAX;
const auto & p1=find_path(dist1,len,&cal_path,&cal_time);
for(int i=0;i<N;i  ) dist1[i]=INT_MAX;
const auto & p2=find_path(dist1,u_time,&cal_time,&cal_intersections );
if(p1==p2)
{
printf("Distance = %d; Time = %d: ",cal_path(p1),cal_time(p1));
print_path(p1);
}
else{
printf("Distance = %d: ",cal_path(p1));
print_path(p1);
printf("Time = %d: ",cal_time(p2));
print_path(p2);
}
return 0;
}``````