香甜的黄油（信息学奥赛一本通 |
您所在的位置：网站首页 › 最新的黄油是多少号 › 香甜的黄油（信息学奥赛一本通 |
|
题目描述 农夫 John 发现做出全威斯康辛州最甜的黄油的方法：糖。 把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。 当然，他将付出额外的费用在奶牛上。 农夫 John 很狡猾，像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。 他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫 John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。 给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。 输入格式 第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。 第二行到第 N + 1 行: 1 到 N 头奶牛所在的牧场号。 第 N + 2 行到第 N + C + 1 行：每行有三个数：相连的牧场 A、B，两牧场间距，当然，连接是双向的。 输出格式 奶牛必须行走的最小的距离和。 输入样例 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 输出样例 8 数据范围 1 ≤ N ≤ 500 2 ≤ P ≤ 800 1 ≤ C ≤ 1450 1 ≤ D ≤ 255 题解 SPFA && 链式前向星： 解题步骤： 枚举所有牧场的编号，将其最为起点；每次枚举都跑一次最短路，累加其他牧场到起点的距离，答案就是所有距离之和的最小值；由于要枚举所有的牧场，因此要使用 dijkstra (堆优化) 或 spfa ； #include #include #include using namespace std; const int N = 810, M = 3010, INF = 0x3f3f3f3f; int n, p, c; bool st[N]; int dist[N], id[N]; int h[N], e[M], w[M], ne[M], idx; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } int spfa(int start) { memset(dist, 0x3f, sizeof dist); dist[start] = 0; queue q; q.push(start), st[start] = true; while(q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if(dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if(!st[j]) { q.push(j); st[j] = true; } } } } int sum = 0; for (int i = 1; i cin >> n >> p >> c; for (int i = 1; i > id[i]; memset(h, -1, sizeof h); while(c --) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } int ans = INF; for (int i = 1; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |