ac日记——香甜的黄油codevs2038

关键词：

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

样例图形

         P2  
P1 @[email protected] C1
        |        |       5  7  3
        |           |     C3
      C2 @[email protected]
         P3    P4

8

{说明： 放在4号牧场最优. }

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define INF 0x7ffffff

using namespace std;

struct EdgeType {
    int to,dis,next;
};
struct EdgeType edge[3005];

int n,p,m,bel[805],cnt,ans=INF;
int head[805],dis[805],que[3005];

bool if_[805];

char Cget;

inline void in(int &now)
{
    now=0,Cget=getchar();
    while(Cget>‘9‘||Cget<‘0‘) Cget=getchar();
    while(Cget>=‘0‘&&Cget<=‘9‘)
    {
        now=now*10+Cget-‘0‘;
        Cget=getchar();
    }
}

int main()
{
    in(n),in(p),in(m);int u,v,w;
    for(int i=1;i<=n;i++) in(bel[i]);
    for(int i=1;i<=m;i++)
    {
        in(u),in(v),in(w);
        edge[++cnt].to=v,edge[cnt].next=head[u],edge[cnt].dis=w,head[u]=cnt;
        edge[++cnt].to=u,edge[cnt].next=head[v],edge[cnt].dis=w,head[v]=cnt;
    }
    for(int s=1;s<=p;s++)
    {
        for(int i=1;i<=p;i++) dis[i]=INF;
        int he=0,ta=0;if_[s]=true,dis[s]=0;
        que[ta++]=s;
        while(he<ta)
        {
            int pos=que[he];he++;
            for(int i=head[pos];i;i=edge[i].next)
            {
                if(dis[edge[i].to]>dis[pos]+edge[i].dis)
                {
                    dis[edge[i].to]=dis[pos]+edge[i].dis;
                    if(!if_[edge[i].to])
                    {
                        if_[edge[i].to]=true;
                        que[ta++]=edge[i].to;
                    }
                }
            }
            if_[pos]=false;
        }
        int tot=0;
        for(int i=1;i<=n;i++) tot+=dis[bel[i]];
        if(tot<ans) ans=tot;
    }
    cout<<ans;
    return 0;
}

codevs2038香甜的黄油x+luogup1828x

题目描述Description农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很... 查看详情

2038香甜的黄油

2038香甜的黄油USACO时间限制:1s空间限制:128000KB题目等级:钻石Diamond   题目描述Description农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能... 查看详情

香甜的黄油

题目描述 Description农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫Jo... 查看详情

香甜的黄油真

1#include<iostream>2#include<cstdio>3#include<queue>4#include<cstring>5usingnamespacestd;6#definemaxn0x7fffffff;7intmap[1000][1000];8inta[1000][1000];9intdis[1000];10intn,mc,m; 查看详情

cogs309香甜的黄油

题目描述农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很狡猾。像... 查看详情

ac日记——字典codevs4189

4189字典  时间限制:1s 空间限制:256000KB 题目等级:大师Master题解 查看运行结果  题目描述 Description最经,skyzhong得到了一本好厉害的字典，这个字典里整整有n个单词(1<=n<=200000)现在skyzhong需要在字典... 查看详情

1127.香甜的黄油最短路(代码片段)

https://www.acwing.com/problem/content/description/1129/对于每一个Dijkstra()，然后算总花费中，最小的总花费即可。#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedeflongl 查看详情

ac日记——绿豆蛙的归宿codevs2488

绿豆蛙的归宿  思路：　　topsort+期望dp； 代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definemaxn100005inthead[maxn],cnt,E[maxn&l 查看详情

ac日记——接龙游戏codevs1051

1051接龙游戏  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond   题目描述 Description给出了N个单词，已经按长度排好了序。如果某单词i是某单词j的前缀，i->j算一次接龙(两个相同的单词不能算接... 查看详情

ac日记——无线网络发射器选址洛谷p2038

题目描述随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的... 查看详情

ac日记——刺激codevs1958

时间限制:1s空间限制:128000KB题目等级:黄金Gold  题目描述 Descriptionsaffah的一个朋友S酷爱滑雪，并且追求刺激（exitement，由于刺激过度导致拼写都缺了个字母），喜欢忽高忽低的感觉。现在S拿到了一张地图，试图制定一... 查看详情

ac日记——丑数codevs1246

1246丑数 USACO 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description对于一给定的素数集合S={p1,p2,...,pK}, 来考虑那些质因数全部属于S的数的集合。这个集合包括... 查看详情

ac日记——中庸之道codevs2021

2021中庸之道  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description给定一个长度为N的序列，有Q次询问，每次询问区间[L,R]的中位数。数据保证序列中任意两个数不... 查看详情

[cogs309][usaco3.2]香甜的黄油

★★  输入文件：butter.in  输出文件：butter.out  简单对比时间限制：1s  内存限制：128MB描述农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶... 查看详情

洛谷p1828香甜的黄油sweetbutter题解

此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。题目链接：https://www.luogu.org/problem/show?pid=1828题目描述农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=... 查看详情

ac日记——爱情之路codevs2070

2070爱情之路  时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解   题目描述 Description yh非常想念他的女朋友小y，于是他决定前往小y所在的那块大陆。小y所在的大陆共有n个城市，m条双向路，... 查看详情

ac日记——绿色通道codevs3342

3342绿色通道  时间限制:1s 空间限制:256000KB 题目等级:黄金Gold题解 查看运行结果  题目描述 Description《思远高考绿色通道》(GreenPassage,GP)是唐山一中常用的练习册之一，其题量之大深受lsz等许多oiers的... 查看详情

ac日记——爱改名的小融codevs2967

2967爱改名的小融  时间限制:1s 空间限制:16000KB 题目等级:白银Silver题解   题目描述 DescriptionWikioi上有个人叫小融，他喜欢改名。他的名字都是英文，只要按顺序出现R,K,Y三个字母，就是他的名字。给... 查看详情