PAT甲级 1111 Online Map 单源最短路+DFS

题目大意：

给出一张图有n个结点，m条边，每条边有自己的长度以及需要的时间（长度和时间没有必然联系），有些边是有向边，有些边是无向边，再给出起点和终点，我们要求出距离最短的路径和花费时间最少的路径，若两条路径距离相同，我们要选择花费时间最少的，若两条路径花费时间相同，我们要选择经过结点数最少的。如果最后要求的两条路径是相同的，我们只输出一条路径信息即可。

代码如下：

//单源最短路+DFS

#include<iostream>
#include<math.h>
#include<vector>
#include<stdio.h>
#define INF 0x3f3f3f3f
#define MAX 505
using namespace std;

int mp[MAX][MAX];
int cost[MAX][MAX];
int visit[MAX];
int dis[MAX];

int n,m;
int s,f;//起点与终点
vector<int> path,temppath,lastpath;
int last_dis;
int min_time=INF,min_num=INF;


struct edge{
    int a,b;
    int len;
    int flag;
    int time;
};

vector<edge> vec;
vector<int> pre[MAX];

void dijkstra1(int s){//求最短路径
    for(int i=0;i<n;i++){
        visit[i]=0;
        dis[i]=INF;
    }

    dis[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,minl=INF;
        for(int j=0;j<n;j++){
            if(dis[j]<minl&&visit[j]==0){
                u=j;
                minl=dis[j];
            }
        }
        if(u==-1){
            break;
        }
        visit[u]=1;

        for(int v=0;v<n;v++){
            if(visit[v]==0&&mp[u][v]!=INF){
                if(dis[v]>dis[u]+mp[u][v]){
                    dis[v]=dis[u]+mp[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v]==dis[u]+mp[u][v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

void dijkstra2(int s){
    for(int i=0;i<n;i++){
        visit[i]=0;
        dis[i]=INF;
        pre[i].clear();
    }

    dis[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,minl=INF;
        for(int j=0;j<n;j++){
            if(dis[j]<minl&&visit[j]==0){
                u=j;
                minl=dis[j];
            }
        }
        if(u==-1){
            break;
        }
        visit[u]=1;

        for(int v=0;v<n;v++){
            if(visit[v]==0&&cost[u][v]!=INF){
                if(dis[v]>dis[u]+cost[u][v]){
                    dis[v]=dis[u]+cost[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v]==dis[u]+cost[u][v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}



void dfs1(int v){
    temppath.push_back(v);
    if(v==s){
        int total=0;//记录时间
        for(int i=0;i<temppath.size()-2;i++){
            total+=cost[temppath[i+1]][temppath[i]];
        }
        if(total<min_time){
                min_time=total;
                path=temppath;
        }
        temppath.pop_back();
        return;
    }

    for(int i=0;i<pre[v].size();i++){
        dfs1(pre[v][i]);
    }
    temppath.pop_back();
}

void dfs2(int v){//求最短时间
   temppath.push_back(v);
    if(v==s){
        int total=temppath.size();//记录经过的点数
        if(total<min_num){
            min_num=total;
            path=temppath;
        }
        temppath.pop_back();
        return;
    }

    for(int i=0;i<pre[v].size();i++){
        dfs2(pre[v][i]);
    }
    temppath.pop_back();
}


int main(){
    cin>>n>>m;
    vec.resize(m);
    for(int i=0;i<m;i++){
        cin>>vec[i].a>>vec[i].b>>vec[i].flag>>vec[i].len>>vec[i].time;
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            mp[i][j]=INF;
            cost[i][j]=INF;
        }
    }

    for(int i=0;i<m;i++){
        if(vec[i].flag==1){
            mp[vec[i].a][vec[i].b]=vec[i].len;
            cost[vec[i].a][vec[i].b]=vec[i].time;
        }else{
            mp[vec[i].a][vec[i].b]=mp[vec[i].b][vec[i].a]=vec[i].len;
            cost[vec[i].a][vec[i].b]=cost[vec[i].b][vec[i].a]=vec[i].time;
        }
    }

    cin>>s>>f;

    dijkstra1(s);
    dfs1(f);
    last_dis=dis[f];
    lastpath=path;
    temppath.clear(),path.clear();

    dijkstra2(s);
    dfs2(f);


    if(path!=lastpath){
        cout<<"Distance = "<<last_dis<<": ";
        for(int i=lastpath.size()-1;i>=0;i--){
            if(i==0){
                cout<<lastpath[i];
            }else{
                cout<<lastpath[i]<<" -> ";
            }
        }
        cout<<endl;
        cout<<"Time = "<<dis[f]<<": ";
        for(int i=path.size()-1;i>=0;i--){
            if(i==0){
                cout<<path[i];
            }else{
                cout<<path[i]<<" -> ";
            }
        }
    }else{
        cout<<"Distance = "<<last_dis<<"; Time = "<<dis[f]<<": ";
        for(int i=path.size()-1;i>=0;i--){
            if(i==0){
                cout<<path[i];
            }else{
                cout<<path[i]<<" -> ";
            }
        }
    }


    return 0;


}