看到这题，第一印象，用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分代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
struct E
{
int u,v,w;
}edge[];
struct Node
{
int n,w;
bool operator<(const Node&t)const{
return w>t.w;
}
};
priority_queue<int,vector<int>,greater<int> >d[];
int book[],next[+],first[];
int n,m,k;
void Dijkstra(int x)
{
priority_queue<Node>Q;
int dis[];
for(int i=;i<n;i++){
dis[i]=inf;
}
dis[x]=;
Q.push((Node){x,});
while(!Q.empty()){
Node t=Q.top();Q.pop();
if(t.w!=dis[t.n])continue;
d[t.n].push(t.w);
int p=first[t.n];
while(p!=-){
E&e=edge[p%];
int u=e.v;
if(u==t.n)u=e.u;
if(dis[u]>dis[t.n]+e.w){
dis[u]=dis[t.n]+e.w;
Q.push((Node){u,dis[u]});
}
p=next[p];
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
int j=;
for(int i=;i<n;i++){
int x;
scanf("%d",&x);
if(x)book[j++]=i;
first[i]=-;
}
book[j]=-;
for(int i=;i<m;i++){
int&u=edge[i].u,&v=edge[i].v,&w=edge[i].w;
scanf("%d%d%d",&u,&v,&w);
u--;v--;
next[i]=first[u];
first[u]=i;
next[i+]=first[v];
first[v]=i+;
}
for(int i=;book[i]!=-;i++){
Dijkstra(book[i]);
}
for(int i=;i<n;i++){
ll ans=;int cnt=k;
while(!d[i].empty()&&cnt--){
ans+=d[i].top();
d[i].pop();
}
printf("%lld\n",ans);
}
return ;
}
不过还是很想知道究竟怎样才能满分啊QAQ 求指教Orz