题328.单源最短路的扩展应用-acwing-Q1137--选择最佳线路

文章目录

• 题328.单源最短路的扩展应用-acwing-Q1137--选择最佳线路
• 一、题目
• 二、题解

---

题328.单源最短路的扩展应用-acwing-Q1137–选择最佳线路

---

一、题目

二、题解

本题要你在可选的起点车站中选择一个起点出发使得达到终点s的距离最小，输出这个最小距离。显然直接去想我们可以对每一个可选择的起点做一次单源最短路，然后求到终点的最小距离，但是这样时间复杂度过高。
更快的办法其实可以建立一个虚拟源点，将它和所有可供选择的起点连一条边权为0的边，然后对这个虚拟源点做一遍单源最短路算法。或者，其实可以反向建图，然后将终点s当作源点做单源最短路，之后去用一层循环找到那个最佳选择即可。
代码如下：

//法一:虚拟源点法
#include 

using namespace std;

const int maxn=1100,maxm=21000;
const int Inf=0x3f3f3f3f;

int n,m,s;
int h[maxn],e[maxm],w[maxm],ne[maxm],idx;
int dist[maxn],book[maxn];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa()
{
    fill(dist,dist+maxn,Inf);
    queue<int> q;
    dist[0]=0;
    q.push(0);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        book[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!book[j])
                {
                    q.push(j);
                    book[j]=1;
                }
            }
        }
    }
    if(dist[s]==Inf)
    {
        return -1;
    }
    else
    {
        return dist[s];
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=-1)//
    {
        fill(h,h+maxn,-1);//初始化表头
        idx=0;//初始化边数
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        int w;
        scanf("%d",&w);
        for(int i=0;i<w;i++)
        {
            int v;
            scanf("%d",&v);
            add(0,v,0);//将可选择的出发地和虚拟源点0连上一条边权为0的边
        }
        printf("%d\n",spfa());
    }
}

//法二：反向建图，终点做为源点做单源最短路
#include 

using namespace std;

const int maxn=1100,maxm=21000;
const int Inf=0x3f3f3f3f;

int n,m,s;
int h[maxn],e[maxm],w[maxm],ne[maxm],idx;
int dist[maxn],book[maxn];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int spfa()
{
    fill(dist,dist+maxn,Inf);
    queue<int> q;
    dist[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        book[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!book[j])
                {
                    q.push(j);
                    book[j]=1;
                }
            }
        }
    }
    if(dist[s]==Inf)
    {
        return -1;
    }
    else
    {
        return dist[s];
    }
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=-1)
    {
        fill(h,h+maxn,-1);
        idx=0;
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(b,a,c);
        }
        spfa();
        int w;
        scanf("%d",&w);
        int res=Inf;
        for(int i=0;i<w;i++)//求出可供选择的出发点到s的最小距离
        {
            int v;
            scanf("%d",&v);
            res=min(res,dist[v]);
        }
        if(res==Inf)
        {
            res=-1;
        }
        printf("%d\n",res);
    }
}

---