专栏首页饶文津的专栏【USACO 3.2】Sweet Butter(最短路)

【USACO 3.2】Sweet Butter(最短路)

题意

一个联通图里给定若干个点,求他们到某点距离之和的最小值。

题解

枚举到的某点,然后优先队列优化的dijkstra求最短路,把给定的点到其的最短路加起来,更新最小值。复杂度是

(O(NElogE))

。 注意此题给的n是奶牛个数,p是牧场个数,p才是点的个数N,所以head、dis、vis要开到1000。

代码

/*
USER:19flipp1
TASK:butter
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define in(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout);
#define ll long long
#define N 1005
#define M 3000
#define inf 0x3f3f3f3f
using namespace std;
int n,p,c,pos[N];
struct edge{
    int to,next,w;
}e[M];
int head[N],cnt;
void add(int u,int v,int w){
    e[cnt]=edge{v,head[u],w};
    head[u]=cnt++;
}
struct qnode{
    int v,c;
    int operator<(const qnode& r)const{
        return c>r.c;
    }
};
int d[N],vis[N];
int dijkstra(int s){
    for(int i=1;i<=p;i++){d[i]=inf;vis[i]=0;}
    priority_queue<qnode>que;
    while(!que.empty())que.pop();
    d[s]=0;
    que.push((qnode){s,0});
    while(!que.empty()){
        int u=que.top().v;
        que.pop();
        if(vis[u])continue;
        vis[u]=1;

        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to,w=e[i].w;
            if(!vis[v]&&d[v]>d[u]+w){
                d[v]=d[u]+w;
                que.push((qnode){v,d[v]});
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans+=d[pos[i]];
    return ans;
}
int main(){
    in(butter);
    memset(head,-1,sizeof head);
    scanf("%d%d%d",&n,&p,&c);
    for(int i=1;i<=n;i++)scanf("%d",&pos[i]);
    for(int i=1;i<=c;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    int ans=inf;
    for(int i=1;i<=p;i++){
        int tans=dijkstra(i);
        ans=min(ans,tans);
    }
    printf("%d\n",ans);
    return 0;
}
/*
          P2
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

*/

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津
  • BUPT2017 wintertraining(15) #1 题解

    求逆元。以前写过题解,http://www.cnblogs.com/flipped/p/5193777.html

    饶文津
  • 【奇技淫巧】-- 走地图的不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    看、未来
  • P2015 二叉苹果树 树状dp

    用户2965768
  • 修理牛棚 Barn Repair

    分析:贪心,取对间隔进行排序,按照贪心思想取间隔最大着为空隙,当前所需木板数+1,要注意的是一旦选出空隙总长要加一,因为你分裂了线段少算了末端,木板数用完了就得...

    glm233
  • P1036 选数

    用户7727433
  • AtCoder Beginner Contest 177 A ~ E

    C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:

    用户7727433
  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津

扫码关注云+社区

领取腾讯云代金券