香甜的黄油

小范围多源转单源最短路 T3

题目描述

P1828 [USACO3.2]香甜的黄油 Sweet Butter - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 香甜的黄油 Sweet Butter - 洛谷 P1828 - Virtual Judge (csgrandeur.cn) Farmer John 发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 $N$ 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

Farmer John 很狡猾。像以前的 Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

Farmer John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入格式

第一行包含三个整数 $N,P,C$，分别表示奶牛数、牧场数和牧场间道路数。

第二行到第 $N+1$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i-1$ 头奶牛所在的牧场号。

第 $N+2$ 行到第 $N+C+1$ 行，每行包含三个整数 $A,B,D$，表示牧场号为 $A$ 和 $B$ 的两个牧场之间有一条长度为 $D$ 的双向道路相连。

输出格式

输出一行一个整数，表示奶牛必须行走的最小的距离和。

样例 #1

样例输入 #1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

样例输出 #1

8

提示

数据范围

对于所有数据，$1\le N\le 500$，$2\le P\le 800$，$1\le A,B\le P$，$1\le C\le 1450$，$1\le D\le 255$。

---

样例解释

作图如下：

          P2  
P1 @--1--@ C1
         |
         | 
       5  7  3
         |   
         |     C3
       C2 @--5--@
          P3    P4

把糖放在4号牧场最优。

思路

题意要求找出一个点, 到指定点的路径和最小。通常解法是用floyd求出以每个点为起点的最短路径, 然后再以$O(NP)$的复杂度找出最小的那个起点。

但floyd本身的复杂度为 $P^3=256\times 10^6$ 会超时, 只能再看看其他最短路模型了。 朴素版dijkstra复杂度为$O(P^2)$, 但这里需要从每个点开始求一次, 故复杂度和floyd一样。 堆优化dijkstra复杂度为$O(C\log P)$ , 这里则为 $CP\log P=1450\times 800\times \log 800=1160000\times 10$ , 大概在 $1e7$左右, 可以过。 spfa复杂度为$O(C)$, 这里则为 $O(PC)$, 大概在$1e6$左右, 代码还短, 可以过, 不过最坏情况为 $O(P^{2}C)$ , 通常不会遇到。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 810, M = 1450 * 2 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int id[N];
int dist[N];
bool st[N];
int n, p, c;
 
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
 
int spfa(int start)
{
    static int q[N];
    int hh = 0, tt = 1;
    memset(dist, 0x3f, sizeof dist);
    q[0] = start;
    dist[start] = 0;
    st[start] = true;
    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;
                }
            }
        }
    }
 
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        int j = id[i];
        if (dist[j] == INF)
        {
            res = INF;
            break;
        }
        res += dist[j];
    }
    return res;
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> p >> c;
 
    for (int i = 0; i < n; i++)
        cin >> id[i];
    while (c--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    int res = INF;
    for (int i = 1; i <= p; i++)
        res = min(res, spfa(i));
 
    cout << res << endl;
    return 0;
}