看到这题，第一印象，用dijkstra算法求n次单源最短路，时间复杂度O(n^3)，超时30分妥妥的。
于是用优先队列优化，O(n*mlogm)，快很多，但依然30。
那么不妨换一种思路，题目要求的是任一据点到最近k个行星发动机据点的最短路之和，也就是说我们不必求出所有的最短路，而只需要求出各行星发动机据点到其它据点的最短路。
若行星发动机据点个数为t，则只需求t次最短路，这样一来，时间复杂度变为O(t*mlogm)。
又见子任务：对于60%的数据 保证行星发动机数量和k相同。
于是，有60分的数据时间复杂度可降到O(k*mlogm)，大约10^7，这60分算是稳了！
我是用邻接表存储图。然后把每次求出的最短路push进n个优先队列，Dijkstra结束后对n个据点从小到大出栈、求和并输出。
60分代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<vector> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 const int inf=0x3f3f3f3f; 10 struct E 11 { 12 int u,v,w; 13 }edge[10000]; 14 struct Node 15 { 16 int n,w; 17 bool operator<(const Node&t)const{ 18 return w>t.w; 19 } 20 }; 21 priority_queue<int,vector<int>,greater<int> >d[10000]; 22 int book[10001],next[20000+5],first[10000]; 23 int n,m,k; 24 void Dijkstra(int x) 25 { 26 priority_queue<Node>Q; 27 int dis[10000]; 28 for(int i=0;i<n;i++){ 29 dis[i]=inf; 30 } 31 dis[x]=0; 32 Q.push((Node){x,0}); 33 while(!Q.empty()){ 34 Node t=Q.top();Q.pop(); 35 if(t.w!=dis[t.n])continue; 36 d[t.n].push(t.w); 37 int p=first[t.n]; 38 while(p!=-1){ 39 E&e=edge[p%10000]; 40 int u=e.v; 41 if(u==t.n)u=e.u; 42 if(dis[u]>dis[t.n]+e.w){ 43 dis[u]=dis[t.n]+e.w; 44 Q.push((Node){u,dis[u]}); 45 } 46 p=next[p]; 47 } 48 } 49 } 50 int main() 51 { 52 //freopen("in.txt","r",stdin); 53 scanf("%d%d%d",&n,&m,&k); 54 int j=0; 55 for(int i=0;i<n;i++){ 56 int x; 57 scanf("%d",&x); 58 if(x)book[j++]=i; 59 first[i]=-1; 60 } 61 book[j]=-1; 62 for(int i=0;i<m;i++){ 63 int&u=edge[i].u,&v=edge[i].v,&w=edge[i].w; 64 scanf("%d%d%d",&u,&v,&w); 65 u--;v--; 66 next[i]=first[u]; 67 first[u]=i; 68 next[i+10000]=first[v]; 69 first[v]=i+10000; 70 } 71 for(int i=0;book[i]!=-1;i++){ 72 Dijkstra(book[i]); 73 } 74 for(int i=0;i<n;i++){ 75 ll ans=0;int cnt=k; 76 while(!d[i].empty()&&cnt--){ 77 ans+=d[i].top(); 78 d[i].pop(); 79 } 80 printf("%lld\n",ans); 81 } 82 return 0; 83 }
不过还是很想知道究竟怎样才能满分啊QAQ 求指教Orz
原文：https://www.cnblogs.com/zbhfz/p/11331659.html