---

题265.2022分队天梯赛训练-7-38 天梯地图 (30 分)

---

一、题目

二、题解

本题其实就是要你解决两个问题，一个是求最快最短的路,，一个是求最短，途经节点数最少的路。说白了就是写两个双关键字的单源最短路算法就好。代码（这里单源最短路算法采用朴素dij）如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn=510;
const int Inf=0x3f3f3f3f;

int N,M;
int d[maxn][maxn],t[maxn][maxn];
int d_dist[maxn],t_dist[maxn],num[maxn];
int collected[maxn];
int path[maxn];
int S,T;

int findMinTimedist()
{
    int minv,mindist=Inf;
    for(int v=0;v<N;v++)
    {
        if(!collected[v]&&t_dist[v]<mindist)
        {
            mindist=t_dist[v];
            minv=v;
        }
    }
    if(mindist==Inf)
    {
        return -1;
    }
    else
    {
        return minv;
    }
}

int findMinLendist()
{
    int minv,mindist=Inf;
    for(int v=0;v<N;v++)
    {
        if(!collected[v]&&d_dist[v]<mindist)
        {
            mindist=d_dist[v];
            minv=v;
        }
    }
    if(mindist==Inf)
    {
        return -1;
    }
    else
    {
        return minv;
    }
}

void dijkstra_time()//针对时间
{
    fill(collected,collected+maxn,0);
    fill(path,path+maxn,-1);
    for(int v=0;v<N;v++)
    {
        d_dist[v]=d[S][v];
        t_dist[v]=t[S][v];
        if(d[S][v]<Inf&&t[S][v]<Inf)
        {
            path[v]=S;
        }
    }
    d_dist[S]=0;
    t_dist[S]=0;
    path[S]=-1;
    while(1)
    {
        int v=findMinTimedist();
        if(v==-1)
        {
            break;
        }
        collected[v]=1;
        for(int w=0;w<N;w++)
        {
            if(!collected[w]&&d[v][w]<Inf&&t[v][w]<Inf)
            {
                if(t_dist[w]>t_dist[v]+t[v][w])
                {
                    t_dist[w]=t_dist[v]+t[v][w];
                    d_dist[w]=d_dist[v]+d[v][w];
                    path[w]=v;
                }
                else if(t_dist[w]==t_dist[v]+t[v][w]&&d_dist[w]>d_dist[v]+d[v][w])//时间相同看路径长度谁更小
                {
                    d_dist[w]=d_dist[v]+d[v][w];
                    path[w]=v;
                }
            }
        }
    }
}

void dijkstra_len()//针对路径长度
{
    fill(collected,collected+maxn,0);
    fill(path,path+maxn,-1);
    for(int v=0;v<N;v++)
    {
        d_dist[v]=d[S][v];
        if(d[S][v]<Inf&&t[S][v]<Inf)
        {
            path[v]=S;
            num[v]=num[S]+1;
        }
    }
    d_dist[S]=0;
    path[S]=-1;
    num[S]=0;
    while(1)
    {
        int v=findMinLendist();
        if(v==-1)
        {
            break;
        }
        collected[v]=1;
        for(int w=0;w<N;w++)
        {
            if(!collected[w]&&d[v][w]<Inf&&t[v][w]<Inf)
            {
                if(d_dist[w]>d_dist[v]+d[v][w])
                {
                    d_dist[w]=d_dist[v]+d[v][w];
                    num[w]=num[v]+1;
                    path[w]=v;
                }
                else if(d_dist[w]==d_dist[v]+d[v][w]&&num[w]>num[v]+1)//路径长度相同看途经节点数谁更小
                {
                    num[w]=num[v]+1;
                    path[w]=v;
                }
            }
        }
    }
}

int main()
{
    fill(d[0],d[0]+maxn*maxn,Inf);
    fill(t[0],t[0]+maxn*maxn,Inf);
    cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int v1,v2,flag,len,time;
        cin>>v1>>v2>>flag>>len>>time;
        d[v1][v2]=len;
        t[v1][v2]=time;
        if(!flag)
        {
            d[v2][v1]=len;
            t[v2][v1]=time;
        }
    }
    cin>>S>>T;
    vector<int> path1,path2;
    dijkstra_time();
    int now;
    now=T;
    path1.push_back(now);
    while(path[now]!=-1)
    {
        now=path[now];
        path1.push_back(now);
    }
    reverse(path1.begin(),path1.end());
    dijkstra_len();
    now=T;
    path2.push_back(now);
    while(path[now]!=-1)
    {
        now=path[now];
        path2.push_back(now);
    }
    reverse(path2.begin(),path2.end());
    if(path1==path2)
    {
        printf("Time = %d; Distance = %d:",t_dist[T],d_dist[T]);
        for(int i=0;i<path1.size();i++)
        {
            if(i>0)
            {
                printf(" =>");
            }
            printf(" %d",path1[i]);
        }
    }
    else
    {
        printf("Time = %d:",t_dist[T]);
        for(int i=0;i<path1.size();i++)
        {
            if(i>0)
            {
                printf(" =>");
            }
            printf(" %d",path1[i]);
        }
        putchar('\n');
        printf("Distance = %d:",d_dist[T]);
        for(int i=0;i<path2.size();i++)
        {
            if(i>0)
            {
                printf(" =>");
            }
            printf(" %d",path2[i]);
        }
    }
}

---