大家好,又见面了,我是你们的朋友全栈君。
http://codeforces.com/problemset/problem/986/A
n个点的无向连通图,每个点有一个属性,求每个点到s个不同属性点的最短距离
依稀记得那天晚上我和Menteur-Hxy探讨这道题如何不可做的样子
直观想法当然是每个点出发bfs,找到s个就停止,但这最差是n^2的,不能接受!
解法是多源广搜,注意到货物种类非常小(<=100),所以可以求出每个点获得每种货物的最短距离。
做法是进行k次bfs,对于第i次,起点st是每个种类为i的点,广搜的性质决定了她们的平行关系。
这样就可以求出每种货物到每个点的距离,换言之,就是每个点获得每种货物的代价(最小)
然后对于每个点,答案就是最小的s个啦
无向图注意开两倍边
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; const int MAXN=100005; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } struct Edge{ int next,to; }e[MAXN<<1]; int ecnt,head[MAXN]; inline void add(int x,int y){ e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } int dis[MAXN][102],typ[MAXN]; //dis[i][j] - the minimum cost for town i to get the j-th goods int n,m,k,s; queue<int> Q; void bfs(int x){ for(int i=1;i<=n;i++) if(typ[i]==x) Q.push(i),dis[i][x]=0; while(!Q.empty()){ int top=Q.front();Q.pop(); for(int i=head[top];i;i=e[i].next){ int v=e[i].to; if(dis[v][x]>dis[top][x]+1){ dis[v][x]=dis[top][x]+1; Q.push(v); } } } } void init(){ memset(dis,0x3f,sizeof(dis)); } vector<int> V; int main(){ n=rd();m=rd();k=rd();s=rd(); init(); for(int i=1;i<=n;i++) typ[i]=rd(); int x,y,w; for(int i=1;i<=m;i++){ x=rd();y=rd(); add(x,y);add(y,x); } for(int i=1;i<=k;i++) bfs(i); int ret=0; for(int i=1;i<=n;i++){ V.clear(); for(int j=1;j<=k;j++) V.push_back(dis[i][j]); sort(V.begin(),V.end()); ret=0; for(int j=0;j<s;j++) ret+=V[j]; printf("%d ",ret); } return 0; }
转载于:https://www.cnblogs.com/ghostcai/p/9275282.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107434.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...