首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【USACO 3.2】Sweet Butter(最短路)

【USACO 3.2】Sweet Butter(最短路)

作者头像
饶文津
发布2020-06-02 12:05:16
3560
发布2020-06-02 12:05:16
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

题意

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

题解

枚举到的某点,然后优先队列优化的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

*/
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-11-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档