单源最短路的扩展应用

AcWing 1137. 选择最佳线路

题目

https://www.acwing.com/problem/content/1139/ 已知城市中共包含 n 个车站（编号1~n）以及 m 条公交线路。 每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。 琪琪的朋友住在 s 号车站附近。琪琪可以在任何车站选择换乘其它公共汽车。 请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间。

思路

题目意思是：一开始可以有很多个起点，要求所有这些起点到终点中的最少时间， 可以先加一个虚拟起点0，然后这个虚拟起点到所有起点的距离都是1，这样可以转换为求虚拟起点到终点的最小值。

代码

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=1010,M=21010;
int n,m,T;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],q[N];
bool st[N];

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

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[0]=0;
    int hh=0,tt=1;
    q[0]=0;
    while (hh!=tt)
    {
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q[tt++]=j;
                    if(tt==N)tt=0;
                    st[j]=true;
                }
            }
        }

    }
    if(dist[T]==0x3f3f3f3f) return -1;
    return dist[T];
    
}


int main()
{
    while(scanf("%d%d%d", &n, &m, &T) != -1)
    {
        memset(h,-1,sizeof h);
        idx=0;
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        int s;
        cin>>s;
        while(s--)
        {
            int ver;
            cin>>ver;
            add(0,ver,0);
        }
        cout<<spfa()<<endl;
    }
    return 0;
}