[数据结构与算法]1111 Online Map c++

这奥体就用两次dijkstra算法，两个分开写就行了，两个都是独立的。所以本质上这道题就考的最短路径是否熟练，熟练的话写两次就行了，只是变量太多…

#include<bits/stdc++.h>
using namespace std;
#define maxn 510
int n,m;int source,desti;
int Length[maxn][maxn];
int Time[maxn][maxn];
int Lparent[maxn];
int Tparent[maxn];
vector<int>min_path;vector<int>min_time;

void init(){
    cin>>n>>m;fill(Length[0],Length[0]+maxn*maxn,INT_MAX);
    fill(Time[0],Time[0]+maxn*maxn,INT_MAX);
    for(int i=0;i<m;i++){
        int v1,v2,one_way,length,time;cin>>v1>>v2>>one_way>>length>>time;
        if(one_way==1){
            Length[v1][v2]=length;
            Time[v1][v2]=time;
        }
        else{
            Length[v1][v2]=Length[v2][v1]=length;
            Time[v1][v2]=Time[v2][v1]=time;
        }
    }
}
void L_dfs(int end){
    if(end==source){
        min_path.push_back(end);
        return;
    }

    L_dfs(Lparent[end]);
    min_path.push_back(end);
}

void L_dij(){
    int dis[n];bool visited[n];
    int spend[n];Lparent[source]=source;
    fill(spend,spend+n,0);
    fill(dis,dis+n,INT_MAX);fill(visited,visited+n,0);
    dis[source]=0;
     for(int i=0;i<n;i++){
         int index=-1;int min=INT_MAX;
         for(int j=0;j<n;j++){
             if(!visited[j]&&min>dis[j]){
                 min=dis[j];
                 index=j;
             }
         }
        if(index==-1)return;
        visited[index]=1;
        for(int j=0;j<n;j++){
            if(Length[index][j]!=INT_MAX&&!visited[j]){
                if(dis[j]>dis[index]+Length[index][j]){
                    dis[j]=dis[index]+Length[index][j];
                    spend[j]=spend[index]+Time[index][j];
                    Lparent[j]=index;
                }
                else if(dis[j]==dis[index]+Length[index][j]){
                    if(spend[j]>spend[index]+Time[index][j]){
                        spend[j]=spend[index]+Time[index][j];
                        Lparent[j]=index;
                    }

                }
            }
        }
     }

    L_dfs(desti);
}

void T_dfs(int end){
    if(end==source){
        min_time.push_back(end);
        return;
    }
    T_dfs(Tparent[end]);
    min_time.push_back(end);
}

void T_dij(){
    int dis[n];bool visted[n];fill(dis,dis+n,INT_MAX);dis[source]=0;
    fill(visted,visted+n,0);
    Tparent[source]=source;
    int count[n];count[source]=1;
    for(int i=0;i<n;i++){
        int index=-1;int min=INT_MAX;
        for(int j=0;j<n;j++){
            if(!visted[j]&&min>dis[j]){
                min=dis[j];
                index=j;
            }
        }
        if(index==-1)return;
        visted[index]=1;

        for(int j=0;j<n;j++){
            if(!visted[j]&&Time[index][j]!=INT_MAX){
                if(dis[j]>dis[index]+Time[index][j]){
                    dis[j]=dis[index]+Time[index][j];
                    count[j]=count[index]+1;
                    Tparent[j]=index;
                }
                else if(dis[j]==dis[index]+Time[index][j]){
                    if(count[j]>count[index]+1){
                        count[j]=count[index]+1;
                        Tparent[j]=index;
                    }
                }
            }
        }
    }

    T_dfs(desti);

}


int main(){
    init();
    cin>>source>>desti;
    L_dij();
    T_dij();

    string s1="",s2="";
    for(int i=0;i<min_path.size();i++){
        if(i!=0)
            s1+=" -> ";
        s1+= to_string(min_path[i]);
    }

    for(int i=0;i<min_time.size();i++){
        if(i!=0)
            s2+=" -> ";
        s2+= to_string(min_time[i]);
    }


    int Distance=0;
    for(int i=0;i<min_path.size()-1;i++)
        Distance+=Length[min_path[i]][min_path[i+1]];
    int Ti=0;
    for(int i=0;i<min_time.size()-1;i++)
        Ti+=Time[min_time[i]][min_time[i+1]];

    
    if(s1!=s2){
        cout<<"Distance = "<<Distance<<": "<<s1;
        cout<<endl;
        cout<<"Time = "<<Ti<<": "<<s2;
    }
    else{
        cout<<"Distance = "<<Distance<<"; "<<"Time = "<<Ti<<": "<<s2;
    }

}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖