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[],tot,head[],nextt[],to[],w[],vis[],d[],ans = ; 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, , sizeof(vis));
memset(d, , sizeof(d));
queue <int> q;
q.push(x);
vis[x] = ;
d[x] = ;
int num = ;
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
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] = ;
q.push(v);
}
}
}
}
for (int i = ; i <= p; i++)
if (a[i] > )
num += a[i] * d[i];
ans = min(num, ans);
} int main()
{
scanf("%d%d%d", &n, &p, &c);
for (int i = ; i <= n; i++)
{
int temp;
scanf("%d", &temp);
a[temp]++;
}
for (int i = ; 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 = ; i <= p; i++)
dfs(i);
printf("%d\n", ans);
//while (1); return ;
}