2017年5月16日 | ljfcnyali
题目大意
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他用额外赚来的钱给奶牛买奢侈品。
农夫John很狡猾。他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场呆着(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)。
Sample Input
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
Sample Output
8
样例图形
P2
P1 @[email protected] C1
\ |\
\ | \
5 7 3
\ | \
\| \ C3
C2 @[email protected]
P3 P4
题目分析
枚举每一个终点,Dijstra进行单源最短路径,因为这样子会超时,所以加上一个堆优化即可。
题目注意
输出要换行。
AC代码
/*
LANG: C++
ID: jerry272
PROG: butter
*/
/*************************************************************************
> File Name: USACO3.2.5-butter.cpp
> Author: ljf-cnyali
> Mail: [email protected]
> Created Time: 2017/5/16 19:20:19
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
#define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
#define mem(a) memset((a), 0, sizeof(a))
#define str(a) strlen(a)
const int inf = << ;
const int maxn = ;
struct Edge{
int from, to, dist;
} ;
struct Node{
int u, d;
bool operator < (const Node& n) const{
return d > n.d;
}
};
vector<Edge> edges;
int d[maxn], cnt[maxn], v[maxn];
int N, M, C;
vector<int> G[maxn];
void Dijksta(int s) {
REP(i, , N)
d[i] = inf, v[i] = ;
d[s] = ;
priority_queue<Node> Q;
Q.push((Node) { s, });
while ( !Q.empty()){
Node x = Q.top();
Q.pop();
int u = x.u;
v[u] = ;
REP(i, , G[u].size() - ) {
Edge& e = edges[G[u][i]];
if(v[e.to]) continue;
if(d[u] + e.dist < d[e.to]) {
d[e.to] = d[u] + e.dist;
Q.push((Node){e.to, d[e.to]});
}
}
}
}
int main() {
freopen("butter.in", "r", stdin);
freopen("butter.out", "w", stdout);
mem(cnt);
int cow, from, to, dist;
cin >> C >> N >> M;
while(C --) {
cin >> cow;
cnt[cow] ++;
}
while(M--) {
cin >> from >> to >> dist;
edges.push_back((Edge){from, to, dist});
edges.push_back((Edge){to, from, dist});
int m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
}
int ans = inf;
REP(i, , N) {
int tans = ;
Dijksta(i);
REP(i, , N)
tans += d[i] * cnt[i];
ans = min(ans, tans);
}
cout << ans << endl;
return ;
}
本文转自:http://ljf-cnyali.cn/index.php/archives/143