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

关键词：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long int LL;
const int N=1e3*4+10;
int dist[N],st[N];
int h[N],e[N],w[N],ne[N],idx;
LL n,m,t,cow[N],ans=1e9;
void add(int a,int b,int c)

    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;

void Dijkstra(int startx)

    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[startx]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push(0,startx);
    while(heap.size())
    
        auto t=heap.top(); heap.pop();
        int u=t.second;
        if(st[u]) continue;
        st[u]=1;
        for(int i=h[u];i!=-1;i=ne[i])
        
            int j=e[i];
            if(dist[j]>dist[u]+w[i])
            
                dist[j]=dist[u]+w[i];
                heap.push(dist[j],j);
            
        
    

int main(void)

    memset(h,-1,sizeof h);
    scanf("%lld%lld%lld",&t,&n,&m);
    for(int i=1;i<=t;i++) scanf("%lld",&cow[i]);
    while(m--)
    
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
       add(a,b,c),add(b,a,c);
    
    for(int i=1;i<=n;i++)
    
        Dijkstra(i);
        LL temp=0;
        for(int j=1;j<=t;j++) temp+=dist[cow[j]];
        if(temp>=0x3f3f3f3f) continue;
        ans=min(ans,temp);
    
    printf("%lld",ans);
    return 0;

usaco3.2.6sweetbutter香甜的黄油(代码片段)

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

香甜的黄油(代码片段)

链接https://www.acwing.com/problem/content/1129/题目农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上... 查看详情

2038香甜的黄油

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

最短路练习(代码片段)

9021#1259香甜的黄油模板题了。稍微有点背景。很好过，不多说。给出点权。边权全部为1。求设在哪个牧场，牛的总移动距离最短。无论是Floyd还是dijistra，都要有一步假设这个牧场为答案进行计算。不算不知道啊，所以几个牧场... 查看详情

香甜的黄油

题目描述 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; 查看详情

ac日记——香甜的黄油codevs2038

2038香甜的黄油 USACO 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果  题目描述 Description农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1&l... 查看详情

codevs2038香甜的黄油

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

算法提高课——图论

...，输出“-1”即可//注意预处理时d[i][i]=0。AcWing1127.香甜的黄油//多源汇最短路问题（可用堆优化Dijkstra或Spfa）//分析数据范围得知，Floyd算法会超时.所以可以枚举每一个点作为起点时的花费AcWing1126.最小花费//注意扣除手续... 查看详情

cogs309香甜的黄油

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

[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<=... 查看详情

codevs2038香甜的黄油x+luogup1828x

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

最短路算法分析(代码片段)

最短路算法分析如下图所示，我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路就是指连接两点的这些路径中最短的一条。对于所有求最短路的算法，都... 查看详情

最短路(代码片段)

最短路要求掌握Floyd,Dijkstra,SPFA下面依次来讲解....... 1：Flyod 弗洛伊德（Floyd）是解决最短路径的算法，可以求出任意两点间的最短路径。使用条件： 　　1:可以出现负边权 　　2:不是单源（只有一个起始点）算法利与弊... 查看详情

最短路(代码片段)

...m条边的无向图，n个点的编号从1~n，定义源点为1。定义最短路树如下：从源点1经过边集T到任意一点i有且仅有一条路径，且这条路径是整个图1到i的最短路径，边集T构成最短路树。给出最短路树，求对于除了源点1外的每个点i，... 查看详情

最短路径问题（最短路模板）(代码片段)

...的直线距离。现在的任务是找出从一点到另一点之间的最短路径。【题目链接】　　　　http://ybt.ssoier.cn:8088/problem_show.php?pid=1342【代码1】Floyd算法O 查看详情

[code+#4]最短路（最短路）(代码片段)

[Code+#4]最短路题目背景在北纬91°，有一个神奇的国度，叫做企鹅国。这里的企鹅也有自己发达的文明，称为企鹅文明。因为企鹅只有黑白两种颜色，所以他们的数学也是以二进制为基础发展的。比如早在1110100111101001年前，他们... 查看详情