原题链接
题意：
n个点，m条边，最多有k个不同类型的物品，要求收集s个不同类型的物品。每个点都会产生一种类型的物品，问从每个点出发收集够s个物品的最短路径之和。
思路：
注意n的范围很大，为1e5：k的范围只有100。
正常思路是从每个点出发跑bfs，这样肯定会T。可以逆向思维，从每种类型的物品出发跑bfs，记录每种类型的物品到达所有城市的最短路径。对于每一个城市，取最小的s个即可。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) #define x first #define y second const int maxn=1e6+7,inf=0x3f3f3f3f; int n,m,s,k,a[maxn]; int h[maxn],idx; struct node{ int e,ne; }edge[maxn]; void add(int u,int v){ edge[idx]={v,h[u]},h[u]=idx++; } vector<int>res[maxn]; bool st[maxn]; void bfs(int k){ queue<PII>q; memset(st,0,sizeof st); rep(i,1,n) if(a[i]==k) st[i]=1,q.push({i,0}); while(!q.empty()){ auto t=q.front();q.pop(); int id=t.first,dis=t.second; res[id].push_back(dis); for(int i=h[id];~i;i=edge[i].ne){ int j=edge[i].e; if(!st[j]){ st[j]=1,q.push({j,dis+1}); } } } } int main() { memset(h,-1,sizeof h); idx=0; n=read,m=read,k=read,s=read; rep(i,1,n) a[i]=read; rep(i,1,m){ int u=read,v=read; add(u,v);add(v,u); } rep(i,1,k) bfs(i); rep(i,1,n){ sort(res[i].begin(),res[i].end()); ll t=0; rep(j,0,s-1) t+=res[i][j]; printf("%lld ",t); } return 0; }
