【题目背景】
“你在平原上走着走着，突然迎面遇到一堵墙，这墙向上无限高，向下无限深，向
左无限远，向右无限远，这墙是什么？”——《流浪地球》原著
我们带着地球去流浪了，为了处理流浪过程中可能会发生的危机，联合政府找到
你，希望你能协助完成 317 号子任务：制定应急预案。
【题目描述】
地球的表面有 n 个据点，这些据点之间存在 m 条双向道路。
这些据点中，有的是建立在行星发动机之下，受到行星发动机的保护（行星发动机
据点），而其他据点则没有行星发动机的保护（普通据点，比如燃料采集据点/科研据点
等）。
当发生危机的时候，没有行星发动机的保护是非常危险的，所以每个人都需要赶到
最近的行星发动机据点寻求庇护，然而行星发动机据点也不一定安全，再加上行星发动
机据点容量有限，所以有些时候得去第二近或者第三近的行星发动机据点。
联合政府找到你，希望你能够计算出每个据点最近的 k 个行星发动机据点，为了
简化问题，你只需要输出每个据点到最近 k 个行星发动机据点的最短距离之和，如果
某个据点能够到达的行星发动机据点不足 k 个，则输出其能到达的所有行星发动机的
最短距离之和。
【输入格式】
从标准输入读入数据。
输入的第一行包含三个用空格隔开的整数 n, m, k ，含义见题目?述，保证 1 ≤ n ≤
104, 0 ≤ m ≤ 104, 1 ≤ k ≤ 102。据点依次编号为 1 到 n 。
第二行包含 n 个整数依次表示每个据点的类型，每个数为 1 或 0 （1 表示对应据
点为行星发动机据点，0 表示普通据点）。
接下来 m 行，每行三个整数 u, v,w 表示有一条长度为 w 的双向道路连接 u 号据点
和 v 号据点，1 ≤ u, v ≤ n, 1 ≤ w ≤ 103 。
可能有重边和自环。
【输出格式】
输出到标准输出。
输出 n 行，每行输出一个整数表示答案（见题目?述）
【样例 1 输入】
7 6 2
1 0 1 0 1 1 0
1 4 1
1 2 3
2 4 4
2 3 5
2 5 7
6 7 5
【样例 1 输出】
8
8
10
10
0
5
【样例 1 解释】
该样例的输入对应的图如下，其中红色点是行星发动机据点，白色点是普通据点。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;cin>>n>>m>>k;
int s[n+1],dp[n+1][n+1];
for(int i=1;i<=n;i++)
{
cin>>s[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
dp[i][j]=0;
}
else
{
dp[i][j]=(1<<30)-1;
}
}
}
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
dp[a][b]=c;dp[b][a]=c;
}
for(int h=1;h<n+1;h++)
{
for(int i=1;i<n+1;i++)
{
for(int j=1;j<n+1;j++)
{
if(dp[i][j]>dp[i][h]+dp[h][j])
{
dp[i][j]=dp[i][h]+dp[h][j];
}
}
}
}
for(int i=1;i<n+1;i++)
{
int l=0,g=0,f,visited[n+1];
memset(visited,0,sizeof(visited));
while(g!=k)
{
int maxn=1<<26;
for(int j=1;j<n+1;j++)
{
if(s[j]==1&&!visited[j]&&maxn>dp[i][j])
{
maxn=dp[i][j];f=j;
}
}
if(maxn==1<<26)
{
break;
}
l+=maxn;visited[f]=1;g++;
}
cout<<l<<endl;
}
return 0;
}
怎么说呢，一开始用的dij超时得了30分，换了Floyd，样例通过了，但是提交上去wa了。上面是floyd的代码，下面附上dij的代码
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int v,c;
};
void init(int *m,int n)
{
for(int i=1;i<=n;i++)
{
m[i]=1<<30;
}
return ;
}
int main()
{
int n,m,h,t=0;cin>>n>>m>>h;
int visited[n+1],d[n+1],sx[n+1];
vector<vector<edge> > ss(n+1);
for(int i=1;i<=n;i++)
{
int k;cin>>k;sx[i]=k;
}
while(m--)
{
edge k;int a,b,c;cin>>a>>b>>c;
k.v=b;k.c=c;ss[a].push_back(k);
k.v=a;ss[b].push_back(k);
}
while(t++<n)
{
int i=0,l=0;
memset(visited,0,sizeof(visited));init(d,n);d[t]=0;
if(sx[t]==1) i++;
int start=t;
while(i!=h)
{
visited[start]=1;
int maxn=1<<30;
for(int j=0;j<ss[start].size();j++)
{
edge k=ss[start][j];
if(d[start]+k.c<d[k.v])
{
d[k.v]=d[start]+k.c;
}
}
for(int j=1;j<=n;j++)
{
if(!visited[j]&&maxn>=d[j])
{
maxn=d[j];start=j;
}
}
if(maxn==1<<30)
{
break;
}
if(sx[start]==1)
{
i++;l+=d[start];
}
}
cout<<l<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/Stickler/p/10790966.html