P1828 香甜的黄油 Sweet Butter
- 241通过
- 724提交
- 题目提供者JOHNKRAM
- 标签USACO
- 难度普及+/提高
提交 讨论 题解
最新讨论
- 我的SPFA为什么TLE。。
- 为什么会放在试炼场usaco背…
题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）
输入输出格式
输入格式：
第一行: 三个数：奶牛数N，牧场数（2<=P<=800），牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的
输出格式：
一行 输出奶牛必须行走的最小的距离和
输入输出样例
输入样例#1：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例#1：
8
说明
{样例图形
P2
P1 @--1--@ C1
|
|
5 7 3
|
| C3
C2 @--5--@
P3 P4
} {说明：
放在4号牧场最优
}
分析：这道题就是一个非常简单的最短路吧，枚举一个点放糖，计算这个点到其他点的长度再乘以其他点的牛的数量，数据比较大，用不了floyd,所以用spfa,唯一让我欣慰的是，spfa竟然写对了.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; int n, p, c,a[1000],tot,head[3000],nextt[3000],to[3000],w[3000],vis[1000],d[1000],ans = 1000000000; void add(int a, int b, int c) { tot++; to[tot] = b; w[tot] = c; nextt[tot] = head[a]; head[a] = tot; } void dfs(int x) { memset(vis, 0, sizeof(vis)); memset(d, 127, sizeof(d)); queue <int> q; q.push(x); vis[x] = 1; d[x] = 0; int num = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (d[u] + w[i] < d[v]) { d[v] = d[u] + w[i]; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } for (int i = 1; i <= p; i++) if (a[i] > 0) num += a[i] * d[i]; ans = min(num, ans); } int main() { scanf("%d%d%d", &n, &p, &c); for (int i = 1; i <= n; i++) { int temp; scanf("%d", &temp); a[temp]++; } for (int i = 1; i <= c; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); add(y, x, z); } for (int i = 1; i <= p; i++) dfs(i); printf("%d ", ans); //while (1); return 0; }