农夫John想要制作威斯康辛州最甜的黄油,他知道把糖放在牧场上可以吸引奶牛。他有 N 头奶牛和 P 个牧场,这些奶牛分布在不同的牧场中。农夫John可以通过训练奶牛,使它们在听到铃声后前往特定的牧场。他想找到一种最短的方式,让所有奶牛都到达一个特定的牧场,以便在晚上挤奶。

给定奶牛所在的牧场和牧场之间的道路信息,你需要找出使所有奶牛到达目标牧场的最短路程和。

输入格式:

  • 第一行包含三个整数:奶牛数 N,牧场数 P,牧场间道路数 C。
  • 接下来 N 行,每行一个整数表示每头奶牛所在的牧场。
  • 接下来 C 行,每行包含三个整数:相连的牧场 A、B 和两牧场间的距离 D,连接是双向的。

输出格式:

  • 一行,输出奶牛必须行走的最小距离和。

数据范围:

  • 1≤N≤500
  • 2≤P≤800
  • 1≤C≤1450
  • 1≤D≤255

输入样例:

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

输出样例:

8

题目分析

Dijkstra; SPFA

代码实现

朴素Dijkstra

  • O(n^3)
#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 1e3, M = 1e4, P = 1e3;

int n, m, p, ans = 0x7fffffff, arr[P], g[N][N];
int dijkstra(int s) {
    int ans = 0;
    int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    bitset <N> st;
    for (int k = 1; k <= n; ++k) {
        int t = -1;
        for (int i = 1; i <= n; ++i)
            if (!st[i] && (dist[i] < dist[t] || t == -1))
                t = i;
        st[t] = 1;
        ans += arr[t] * dist[t];
        for (int i = 1; i <= n; ++i)
            dist[i] = min(dist[i], dist[t] + g[t][i]);
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(g, 0x3f, sizeof g);
    cin >> p >> n >> m;
    for (int i = 1; i <= n; ++i) g[i][i] = 0;
    for (int i = 0; i < p; ++i) {
        int x;
        cin >> x;
        ++arr[x];
    }
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    for (int i = 1; i <= n; ++i) ans = min(ans, dijkstra(i));
    cout << ans;
    return 0;
} 

堆优化Dijkstra

  • O(n m log(n))
#include <iostream>
#include <bitset>
#include <queue>
#include <vector>
#include <cstring>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;
const int N = 1e3, M = 1e4, P = N;

int n, m, p, h[N], e[M], ne[M], w[M], idx, pp[N], ans = 0x7fffffff;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(int s) {
    int ans = 0, cnt = 0;
    bitset <N> st;
    priority_queue <PII, vector <PII>, greater <PII>> heap;    
    int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    heap.push({0, s});
    while(heap.size()) {
        auto t = heap.top(); heap.pop();
        if (st[t.y]) continue;
        st[t.y] = 1;
        cnt += pp[t.y];
        ans += pp[t.y] * t.x;
        for (int i = h[t.y]; ~i; i = ne[i]) {
            if (dist[e[i]] > dist[t.y] + w[i]) {
                dist[e[i]] = dist[t.y] + w[i];
                heap.push({dist[e[i]], e[i]});
            }
        }
    }
    if (cnt == p) return ans;
    return 0x7fffffff;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> p >> n >> m;
    for (int i = 0; i < p; ++i) {
        int x;
        cin >> x;
        ++pp[x];
    }
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= n; ++i)
        ans = min(ans, dijkstra(i));
    cout << ans;
    return 0;
} 

SPFA

  • O(n n m)
#include <iostream>
#include <cstring>
#include <bitset>
#include <queue>
using namespace std;
const int N = 1e3, M = 1e4, P = N;

int p, n, m, pp[P], h[N], e[M], w[M], ne[M], idx, ans = 0x7fffffff;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
} 
int spfa(int s) {
    int ans = 0;
    int dist[N];
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    queue <int> que;
    que.push(s);
    bitset <N> st;
    st[s] = 1;
    while(que.size()) {
        auto t = que.front(); que.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            if (dist[e[i]] > dist[t] + w[i]) {
                dist[e[i]] = dist[t] + w[i];
                if (!st[e[i]]) {
                    que.push(e[i]);
                    st[e[i]] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (pp[i] && dist[i] == 0x3f3f3f3f) return 0x3f3f3f3f;
        ans += pp[i] * dist[i];
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> p >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < p; ++i) {
        int x;
        cin >> x;
        ++pp[x];
    }
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= n; ++i) ans = min(ans, spfa(i));
    cout << ans;
    return 0;
} 
分类: DijkstraSPFA

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status