本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：
输入在第一行给出两个正整数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
作者: 陈越
单位: 浙江大学
时间限制: 300 ms
内存限制: 64 MB

分析：
本题就是单纯的Dijkstra算法，只是对Dijkstra算法的延申。当时间一定或者距离一定的时候，如何去找最短路径或者前驱结点最少的路。下面是代码实现：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
int n,m;
int x,y,s,len,t;
int minlen,mintim;
struct Node{
    int time=MAX;
    int len=MAX;
};
Node G[501][501];
int dist[501];
int disl[501];
int pre[501];
bool vis[501];
int path[501];
int find_min_dis(int dis[]){
    int min_v=-1;
    int min_dis = MAX;
    for(int i = 0; i < n; i++){
        if(vis[i] == false && dis[i] < min_dis){
            min_dis = dis[i];
            min_v = i;
        }
    }
    return min_v;
}
int dijkstra_for_length(int dis[]){
    int V;
    for(int i = 0; i < n; i++){
        dis[i] = G[x][i].len;
        if(dis[i] < MAX){
            path[i] = x;
            pre[i] = 1;
        }
        else{
           path[i] = -1;
           pre[i] = 0;
        }
        vis[i]= false;
    }
    dis[x] = 0;
    vis[x] = true;
    while(1){
        V = find_min_dis(dis);
        if(V==-1)
            break;
        vis[V] = true;
        for(int i = 0; i < n; i++){
            if(!vis[i] && G[V][i].len < MAX){
                if(dis[V] + G[V][i].len < dis[i]){
                    dis[i]=dis[V]+G[V][i].len;
                    path[i]= V;
                    pre[i] = pre[V] + 1;
                }
                else if(dis[V] + G[V][i].len == dis[i]){
                    if(pre[V] + 1 < pre[i]){
                        path[i] = V;
                        pre[i] = pre[V] + 1;
                    }
                }
            }
        }
    }
    return dis[y];
}
int dijkstra_for_time(int dis[]){
    int V;
    for(int i = 0; i < n; i++){
        dis[i] = G[x][i].time;
        if(dis[i] < MAX){
            path[i] = x;
            disl[i] = G[x][i].len;
        }
        else{
            path[i] = -1;
            disl[i] = MAX;
        }
        vis[i]= false;
    }
    dis[x] = 0;
    vis[x] = true;
    while(1){
        V = find_min_dis(dis);
        if(V==-1)
            break;
        vis[V] = true;
        for(int i = 0; i < n; i++){
            if(!vis[i] && G[V][i].time < MAX){
                if(dis[V] + G[V][i].time < dis[i]){
                    dis[i]=dis[V]+G[V][i].time;
                    disl[i] = disl[V] + G[V][i].len;
                    path[i]= V;
                }
                else if(dis[V] + G[V][i].time == dis[i]){
                    if(disl[V] + G[V][i].len < disl[i]){
                        path[i] = V;
                        disl[i] = disl[V] + G[V][i].len;
                    }
                }
            }
        }
    }
    return dis[y];
}
bool judge(stack<int> stim,stack<int> slen){
    if(stim.size()!= slen.size()) return false;
    while(!stim.empty()){
        int a = stim.top(); stim.pop();
        int b = slen.top(); slen.pop();
        if(a!=b) return false;
    }
    return true;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> x >> y >> s >> len >> t;
        G[x][y].time = t; G[x][y].len = len;
        if(!s){
            G[y][x].time = t;
            G[y][x].len = len;
        }
    }
    cin >> x >> y;
    int t = y;
    stack<int> slen;
    stack<int> stim;
    mintim = dijkstra_for_time(dist);
    while(path[y]!=-1){
        stim.push(path[y]);
        y = path[y];
    }
    y = t;
    minlen = dijkstra_for_length(disl);
    while(path[y]!=-1){
        slen.push(path[y]);
        y = path[y];
    }
    if(judge(stim,slen) == false){
        cout <<"Time = "<<mintim << ": ";
        while(!stim.empty()){
            cout << stim.top() << " => ";
            stim.pop();
        }cout << t << endl;

        cout <<"Distance = "<<minlen << ": ";
        while(!slen.empty()){
            cout << slen.top() << " => ";
            slen.pop();
        }cout << t;
    }
    else {
        cout << "Time = " << mintim << "; Distance = " << minlen << ": ";
        while(!stim.empty()){
            cout << stim.top(); stim.pop();
            cout << " => ";
        }
        cout << t;
    }
}