专栏首页数据结构与算法P1828 香甜的黄油 Sweet Butter

P1828 香甜的黄油 Sweet Butter

题目描述

农夫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号牧场最优

}

思路:SPFA+暴力,详解请看字里行间

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring> 
 4 #include<queue>
 5 #define maxn 0x7fffffff; 
 6 using namespace std;
 7 int num[10001];//储存每一个牧场上的奶牛的数量
 8 int map[1001][1001];
 9 int a[1001][1001];//邻接表
10 int numcishu[1001];//每一个点能到达的边的数量 
11 int ans=maxn;//答案;
12 int minnow;//当前的最小值
13 int dis[1001];//储存当前节点到其他节点的最短路 
14 int vis[1001];
15 queue<int>q;
16 int mc;//牧场数 
17 void spfa(int p)//计算p到其他点的路径 
18 {
19     while(q.size()!=0)q.pop();
20     memset(dis,0x7f,sizeof(dis));
21     vis[p]=1;
22     dis[p]=0;
23     q.push(p);
24     while(q.size()!=0)
25     {
26         int k=q.front();
27         for(int j=1;j<=numcishu[k];j++)
28         {
29             if(dis[a[k][j]]>dis[k]+map[k][a[k][j]])//特别注意因为是邻接表储存所以j不一定是k能到达的边 
30             {
31                 dis[a[k][j]]=dis[k]+map[k][a[k][j]];
32                 if(vis[a[k][j]]==0)
33                 {
34                     q.push(a[k][j]);
35                     vis[a[k][j]]=1;
36                 }
37             }
38         }
39         q.pop();
40         vis[k]=0;
41     }
42     minnow=0;
43     for(int i=1;i<=mc;i++)
44     {
45         minnow=minnow+dis[i]*num[i];    
46     }
47     if(minnow<ans)
48     ans=minnow;
49 }
50 int main()
51 {
52     memset(map,0x7f,sizeof(map));
53     int n;//奶牛数
54     
55     int m;//道路的数量 
56     scanf("%d%d%d",&n,&mc,&m);
57     for(int i=1;i<=n;i++)
58     {
59         int p;//奶牛所在牧场的号码
60         scanf("%d",&p);
61         num[p]++; 
62     }
63     for(int i=1;i<=m;i++)
64     {
65         int x,y,z;
66         scanf("%d%d%d",&x,&y,&z);
67         map[x][y]=map[y][x]=z;
68         a[x][++numcishu[x]]=y;
69         a[y][++numcishu[y]]=x;
70     }
71     for(int i=1;i<=mc;i++)
72     {
73         spfa(i);
74     }
75     cout<<ans;
76     return 0;
77 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack
  • BZOJ5249: [2018多省省队联测]IIIDX(线段树 贪心)

    不难发现题目给出的是一个树,其中\(\frac{i}{K}\)是\(i\)的父亲节点

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack
  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • 算法导论2-9章补充几道题

    本篇博文意在对前几章中遗漏的,本人觉得有意思的习题当独拿出来练练手。 1、习题2-4,求逆序对,时间复杂度要求Θ(nlgn) 定义:对于一个有n个不同的数组A,...

    CloudDeveloper
  • 图m着色问题

    1 问题描述:   给定无向图,m种不同的颜色。使每一种着色法使G中每条边的2个顶点不同颜色,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,...

    用户1154259
  • cuda测试二维block的使用

    #include "cuda_runtime.h" #include <stdio.h> #include <stdlib.h> #include <math....

    用户1154259

扫码关注云+社区

领取腾讯云代金券