算法提高课汇总

模型抽象

• $P$个牧场: 图$P$个顶点.

• 牧场间的双向路线: 无向图.

• 至少存在一个牧场和所有牛所在的牧场连通: 有解.

题目要求我们判断以哪个顶点作为终点/起点(无向图中两者可以等价)使得🐄到达的路径最短.
如果用$Floyd$会超时. 可以采用$Spfa$算法, 枚举所有牧场作为起点时单源最短路,并计算所有🐄
从其所在牧场到达起点的路径长度之和.

代码实现 $O(nm)$

#include <cstring>
#include <iostream>

using namespace std;

const int P = 510, N = 810, M = 1450 * 2 + 10, INF = 0x3f3f3f3f;

int n, m, p; //出于习惯这里用n保存顶点数 p保存奶牛数
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
int id[P]; //奶牛所在牧场编号
bool st[N];

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

int spfa(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    int tt = 0, hh = 0;
    q[tt ++] = s, st[s] = true;

    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] )
                {
                    q[tt ++] = v;
                    st[v] = true;
                    if( tt == N )   tt = 0;
                }
            }
        }
    }

    int res = 0;
    for( int i = 1; i <= p; i ++ )
    {
        int c = dist[ id[i] ];
        if( c == INF )  return INF;
        res += c;
    }
    return res;
}

int main()
{
    cin >> p >> n >> m;
    for( int i = 1; i <= p; i ++ )  cin >> id[i];

    memset(h, -1, sizeof h);
    for( int i = 0; i < m; i ++ )
    {
        int u, v, c;
        cin >> u >> v >> c;
        add(u, v, c), add(v, u, c);
    }

    int res = INF;
    for( int i = 1; i <= n; i ++ )  res = min( res, spfa(i) );
    cout << res << endl;

    return 0;
}