L3-007 天梯地图 (30 分)（条件dij

添加链接描述

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int st,ed;
struct node{
    
    int to,length,time;
}t[N];
vector<node>v[N];
vector<int>anstime,anslength;
typedef pair<int,int> pii;
int dist[N],vis[N],path[N],sum[N];
void dijtime(){
    
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({
    0,st});
    memset(dist,0x3f,sizeof dist);
    memset(path,-1,sizeof path);
    memset(vis,0,sizeof vis);
    memset(sum,0,sizeof sum);
    dist[st]=0;
    while(q.size()){
    
        auto p=q.top();
        q.pop();
        if(vis[p.second])continue;
        vis[p.second]=1;
        for(auto it:v[p.second]){
    
            if(dist[it.to]>dist[p.second]+it.time){
    
                // cout<<it.to<<"\n";
                dist[it.to]=dist[p.second]+it.time;
                path[it.to]=p.second;
                sum[it.to]=sum[p.second]+it.length;
                q.push({
    dist[it.to],it.to});
            }
            else if(dist[it.to]==dist[p.second]+it.time){
    
                if(sum[it.to]>sum[p.second]+it.length){
    
                    sum[it.to]=sum[p.second]+it.length;
                    path[it.to]=p.second;
                    q.push({
    dist[it.to],it.to});
                }
            }
        }
    }

}
void dij(){
    
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({
    0,st});
    memset(dist,0x3f,sizeof dist);
    memset(path,-1,sizeof path);
    memset(vis,0,sizeof vis);
    memset(sum,0,sizeof sum);
    dist[st]=0;
    while(q.size()){
    
        auto p=q.top();
        q.pop();
        if(vis[p.second])continue;
        vis[p.second]=1;
        for(auto it:v[p.second]){
    
            if(dist[it.to]>dist[p.second]+it.length){
    
                // cout<<it.to<<"\n";
                dist[it.to]=dist[p.second]+it.length;
                path[it.to]=p.second;
                sum[it.to]=sum[p.second]+1;
                q.push({
    dist[it.to],it.to});
            }
            else if(dist[it.to]==dist[p.second]+it.length){
    
                if(sum[it.to]>sum[p.second]+1){
    
                    sum[it.to]=sum[p.second]+1;
                    path[it.to]=p.second;
                    q.push({
    dist[it.to],it.to});
                }
            }
        }
    }

}
int main(){
    
    int n,m;
    cin>>n>>m;
    while(m--){
    
        int a,b,way,length,time;
        cin>>a>>b>>way>>length>>time;
        v[a].push_back({
    b,length,time});
        if(way==0){
    
            v[b].push_back({
    a,length,time});
        }
    }
    cin>>st>>ed;
    dijtime();
    int TIME=dist[ed];
    int over=ed;
    anstime.push_back(ed);
    while(over!=st){
    
        anstime.push_back(path[over]);
        over=path[over];
    }

    dij();

    // for(int i=anstime.size()-1;i>=0;i--){
    
    // if(i==anstime.size()-1)cout<<": ";
    // else cout<<" => ";
    // cout<<anstime[i];
    // }

    
    int DIS=dist[ed];
    over=ed;
    anslength.push_back(ed);
    while(over!=st){
    
        anslength.push_back(path[over]);
        over=path[over];
    }
    if(anslength==anstime){
    
        printf("Time = %d; Distance = %d",TIME,DIS);
        for(int i=anstime.size()-1;i>=0;i--){
    
        if(i==anstime.size()-1)cout<<": ";
        else cout<<" => ";
        cout<<anstime[i];
    }
    }
    else {
    
        cout<<"Time = "<<TIME;
        for(int i=anstime.size()-1;i>=0;i--){
    
        if(i==anstime.size()-1)cout<<": ";
        else cout<<" => ";
        cout<<anstime[i];
        }
        cout<<"\nDistance = "<<DIS;
        for(int i=anslength.size()-1;i>=0;i--){
    
        if(i==anslength.size()-1)cout<<": ";
        else cout<<" => ";
        cout<<anslength[i];
        }
    }
    return 0;
}