洛谷 P2966 [USACO09DEC] Cow Toll Paths G（排序，Floyd最短路）

题目链接

https://www.luogu.com.cn/problem/P2966

思路

因为$n$只有$250$，我们可以用Floyd求一遍最短路。

我们用两个数组分别记录从$i$到$j$的最小值，$dist[i][j]$表示从$i$到$j$只有边权的最小值，$ans[i][j]$表示从$i$到$j$包含点权的最小值。

我们可以先将所有的点按照点权从小到大排序，通过枚举中间点$k$，不断更新$dist[i][j]$和$ans[i][j]$即可。

每一次询问的答案即为：$ans[s][t]$。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 3e2 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, q;
int dist[N][N], ans[N][N];
struct node
{
    int val, idx;
} p[N];
bool cmp(node a, node b)
{
    return a.val < b.val;
}
void init()
{
    for (int i = 1; i <= n; i++)
    {
        fill(dist[i] + 1, dist[i] + 1 + n, inf);
        fill(ans[i] + 1, ans[i] + 1 + n, inf);
    }
}
void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dist[p[i].idx][p[j].idx] = min(dist[p[i].idx][p[j].idx], dist[p[i].idx][p[k].idx] + dist[p[k].idx][p[j].idx]);
                ans[p[i].idx][p[j].idx] = min(ans[p[i].idx][p[j].idx], dist[p[i].idx][p[j].idx] + max({p[i].val, p[j].val, p[k].val}));
            }
        }
    }
}
void solve(int test_case)
{
    cin >> n >> m >> q;
    init();
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].val;
        p[i].idx = i;
    }
    sort(p + 1, p + 1 + n, cmp);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }
    floyd();
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        cout << ans[s][t] << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve(i);
    }
    return 0;
}

原文地址：https://blog.csdn.net/weixin_74754298/article/details/143762768

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！