只能想到60分做法，前60%据点数量相对不大大约在10^2这个数量级，对于每个据点跑一次dij然后统计下前k小就好了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define pii pair<int,int> 5 #define mp make_pair 6 class Edge{ 7 public: 8 int v,w; 9 Edge(){} 10 Edge(int v,int w){this->v=v;this->w=w;} 11 }; 12 const int maxn=11111; 13 int N,M,K,u,v,w,tot; 14 int type[maxn]; 15 vector<Edge>g[maxn]; 16 vector<int>vi; 17 int d[1025][maxn]; 18 bool vis[maxn]; 19 void gao(int n,int d[]){ 20 memset(d,inf,sizeof(int)*(N+2)); 21 memset(vis,0,sizeof(vis)); 22 d[n]=0; 23 priority_queue<pii,vector<pii>,greater<pii> >q; 24 q.push(mp(0,n)); 25 while(!q.empty()){ 26 int u=q.top().second;q.pop(); 27 if(vis[u])continue; 28 vis[u]=1; 29 for(Edge e:g[u]){ 30 if(d[u]+e.w<d[e.v]){ 31 d[e.v]=d[u]+e.w; 32 q.push(mp(d[e.v],e.v)); 33 } 34 } 35 } 36 } 37 int main(){ 38 scanf("%d%d%d",&N,&M,&K); 39 for(int i=1;i<=N;++i){ 40 scanf("%d",&type[i]); 41 if(type[i]) vi.push_back(i); 42 } 43 for(int i=1;i<=M;++i){ 44 scanf("%d%d%d",&u,&v,&w); 45 g[u].push_back(Edge(v,w)); 46 g[v].push_back(Edge(u,w)); 47 } 48 for(int i=0;i<vi.size();++i){ 49 gao(vi[i],d[i]); 50 } 51 if(vi.size()<K)K=vi.size(); 52 for(int i=1;i<=N;++i){ 53 int sz=vi.size(); 54 vector<int>v; 55 for(int j=0;j<sz;++j){ 56 v.push_back(d[j][i]); 57 } 58 sort(v.begin(),v.end()); 59 int ans=0; 60 for(int j=0;j<K && v[j]!=inf;++j)ans+=v[j]; 61 printf("%d ",ans); 62 } 63 return 0; 64 } 65 /* 66 7 6 2 67 1 0 1 0 1 1 0 68 1 4 1 69 1 2 3 70 2 4 4 71 2 3 5 72 2 5 7 73 6 7 5 74 75 */