算法提高课汇总

题意理解

多个起点一个终点的最短路问题.

反向建图

一个解决思路是反向建图, 则题目转化为单源最短路问题. 问题的解为从终点到所有起点的最短路径中的最小值.

另一个更具有一般性的求解思路是建立虚拟源点.

虚拟源点

考虑构建一个虚拟源点$s$, 其向所有起点连一条有向边, 且边权为$0$.

利用反向建图理解

用反向建图的方式可以简单理解虚拟源点的正确性: 我们知道通过反向建图求解单源最短路可以
得到从终点到任意可选起点$u$的最短路径值$d$, 而从起点$u$到虚拟源点的权值为$0$, 所以从终点到虚拟
源点的最短路径值与到起点$u$的最短路径值相等. 或者我们可以说任意一条从终点到$u$的最短路径,
存在从终点到$s$的最短路径与之一一对应. 将单向边翻转, 即是虚拟源点的求解思路.

普遍性

之所以说虚拟源点相比反向建图更具有普遍性, 是因为虚拟源点此外还适用于有限起点到有限终点
的最短路问题, 也就是可以在本题的基础上更进一步 — 建立一个虚拟终点, 从所有终点向虚拟终点
连一条单向边,且边权为$0$.

虚拟源点 vs 多源汇最短路

注意这里是有限个起点和终点的最短路径, 而多源汇最短路要求我们求解任意两个顶点的最短路: 也就是所有
顶点都同时作为起点和终点.

代码实现

虚拟源点$+ spfa$

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20000 + N, INF = 0x3f3f3f3f; //注意加上从虚拟源点到有限起点的边数

int n, m, t;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N]; bool st[N]; //spfa

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    int tt = 0, hh = 0;
    q[tt ++] = 0; //起点

    while( hh != tt )
    {
        int u = q[hh ++];
        if( hh == N )   hh = 0;

        st[u] = false;

        for( int i = h[u]; ~i; i = ne[i] )
        {
            int v = e[i];
            if( dist[v] > dist[u] + w[i] )
            {
                dist[v] = dist[u] + w[i];
                if( !st[v] )
                {
                    st[v] = true;
                    q[tt ++] = v;
                    if( tt == N )   tt = 0;
                }
            }
        }
    }
    if( dist[t] == INF )    return -1;
    else    return dist[t];
}

int main()
{
    while( scanf("%d%d%d", &n, &m, &t) != EOF )
    {
        memset(h, -1, sizeof h);
        idx = 0; //注意idx需要重置
        while( m -- )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d", &m);
        while( m -- ) //可选起点
        {
            int s;
            scanf("%d", &s);
            add(0, s, 0); //用0作为虚拟源点
        }
        printf("%d\n", spfa());
    }
    return 0;
}