317号子任务---csp201903-5

一、问题描述二、题目分析三、时间复杂度分析四、AC代码实现五、满分代码

这个题我自己挣扎了很久，最多只能95分，实在拿不了100分，
最后参考别人的博客，使用SPFA算法，拿了100

真就是一步一步探索了很久，后面我也分析了两篇拿100分的博主的代码，学习了一下，确实很佩服他们

试题链接：http://118.190.20.162/view.page?gpid=T85

30分： Floyd和基础dijistra、邻接矩阵表示图
60分： 最短的k个排序得到不优化
80分：cin cout
95分：搞不清楚 scanf printf 优化dijistra 优化找最小k个

求取最短路径时只求行星发动机据点到所有点的最短距离；行星发动机据点->普通点距离 =普通点->行星发动机据点距离使用邻接链表存图，vector数组使用迪杰斯特拉算法，并且使用堆优化，priority求前k个的算法需要优化：具体思路是使用一个大根堆，这个堆的最大大小是k个。在堆的size比k小的时候，向堆中push元素；在堆size>=k的时候，比较堆顶值和到当前行星据点距离，如果堆顶值大于到当前行星据点的距离，就将堆顶pop出，push新的到当前行星据点的距离。这样寻找前k个的复杂度是nklogk。

Floyd算法和Dijistra算法求所有顶点相互间的最短距离：n^3使用堆优化的Dijistra：n* n *logn普通排序查找前k个元素，一般直接用sort：nlogn * k堆优化查找前k个元素：nklogk
这些都是粗略的估计值，具体见另外一篇博客
四种最短路径算法详细分析

85分代码，注释、函数都不敢写，写了分数就会变动

#include
using namespace std;
#define MAXSIZE 10005
#define INFI 100000000
int n,m,k;
typedef struct Node
{
	int id;
	int W;
}AdjNode,*Adj;
struct cmp{
    bool operator()(const Adj a,const Adj b){
        return a->W > b->W;
    }
};
vectorList[MAXSIZE];
int sign[MAXSIZE];
int dist[MAXSIZE];
bool visited[MAXSIZE];
priority_queue>path[MAXSIZE];
priority_queue,cmp>que;   //按边权值从小到大排序队列 

int main()
{
	//cin>>n>>m>>k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&sign[i]);
	}
	for(int i=0;i>u>>v>>w;
		scanf("%d %d %d",&u,&v,&w);
		if(u==v) continue;
		Adj a=new AdjNode;
		a->id=v;
		a->W=w;
		List[u].push_back(a);
		Adj b=new AdjNode;
		b->id=u;
		b->W=w;
		List[v].push_back(b);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(sign[i])
		{
			for(int j=1;j<=n;j++) 
			{
				dist[j]=INFI;
				visited[j]=false;
			}
			dist[i]=0;
			Adj t=new AdjNode;
			t->id=i;
			t->W=0;
			que.push(t);      
			while(!que.empty())
			{
				Adj t_adj=que.top();
				que.pop();   
				if(visited[t_adj->id]) continue; 
				
				int min_i=t_adj->id;
				visited[min_i]=true;
				int len=List[min_i].size();
				for(int j=0;jid;
					if(!visited[t]&&dist[min_i]+List[min_i][j]->WW;
						Adj p=new AdjNode;
						p->id=t;
						p->W=dist[t];
						que.push(p);
					}
				}
			} 
			
			for(int j=1;j<=n;j++)
			{
				if(dist[j]!=INFI) 
				{
					if(path[j].size()dist[j]) 
						{
							path[j].pop();
							path[j].push(dist[j]);
						}
 					}
				}
			}
			
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		int sum=0;
		int j=0;
		while(!path[i].empty())
		{
			sum+=path[i].top();
			path[i].pop();
		}
		printf("%dn",sum);
	}
	return 0;
}

下面这个是相应的解释，代码都是一样的，只不过加了一些注释，交上去分数就不一样

#include
using namespace std;
#define MAXSIZE 10005
#define INFI 100000000
int n,m,k;
typedef struct Node
{
	int id;
	int W;
}AdjNode,*Adj;
struct cmp{   //自定义优先级，返回true表示前者优先级更低（与排序刚好相反） 
    bool operator()(const Adj a,const Adj b){
        return a->W > b->W;
    }
};
vectorList[MAXSIZE];  //vector数组实现邻接表 
int sign[MAXSIZE];
int dist[MAXSIZE];
bool visited[MAXSIZE];
priority_queue>path[MAXSIZE];   //最大堆存每个点所能到达的行星据点的距离 
priority_queue,cmp>que;   //按边权值从小到大排序队列 
void Dijistra()   
{
	for(int i=1;i<=n;i++)
	{
		if(sign[i])   //只判断行星据点到其他点的最短距离 
		{
			for(int j=1;j<=n;j++) //初始化 
			{
				dist[j]=INFI;
				visited[j]=false;
			}
			dist[i]=0;
			Adj t=new AdjNode;
			t->id=i;
			t->W=0;
			que.push(t);      //将起点纳入最小堆中，堆顶元素为到当前到起点最近的点 
			while(!que.empty())  
			{
				Adj t_adj=que.top();  //获得堆顶元素（未收纳的顶点距离起点最近的点） 
				que.pop();   
				if(visited[t_adj->id]) continue;  //该点已经收纳到结果集合了，获取下一个 
				
				int min_i=t_adj->id;
				visited[min_i]=true;  //纳入集合 
				int len=List[min_i].size();
				for(int j=0;jid;
					if(!visited[t]&&dist[min_i]+List[min_i][j]->WW;
						Adj p=new AdjNode;
						p->id=t;
						p->W=dist[t];
						que.push(p);   //将离起点距离变短的点纳入最小堆 
					}
				}
			} 
			
			for(int j=1;j<=n;j++)   //求出每个行星据点到其他所有点的最小距离时就将该距离添加到每个行星据点队列后面 
			{                        //并且只存储前k个，多于k个就将最大堆的堆顶元素拿出来 
				if(dist[j]!=INFI) 
				{
					if(path[j].size()dist[j]) 
						{
							path[j].pop();
							path[j].push(dist[j]);
						}
 					}
				}
			}
			
		}
	}
}
void Solve()    //输出每个据点队列的行星据点距离并求和 
{
	for(int i=1;i<=n;i++)
	{
		int sum=0;
		int j=0;
		while(!path[i].empty())
		{
			sum+=path[i].top();
		//	cout<>n>>m>>k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&sign[i]);   //读入据点类型 
	}
	for(int i=0;i>u>>v>>w;
		scanf("%d %d %d",&u,&v,&w);
		if(u==v) continue;
		Adj a=new AdjNode;  //无向图，两个顶点都要进行操作 
		a->id=v;
		a->W=w;
		List[u].push_back(a);
		Adj b=new AdjNode;
		b->id=u;
		b->W=w;
		List[v].push_back(b);
	}
	Dijistra();
	Solve();
	return 0;
}

自己最终写的：

#include
using namespace std;
#define MAXSIZE 10005
#define INFI 100000000
int n,m,k;
typedef struct Node
{
	int id;
	int W;
}AdjNode,*Adj;
vectorList[MAXSIZE];  //vector数组实现邻接表 
int sign[MAXSIZE];
int dist[MAXSIZE];
bool inq[MAXSIZE];
priority_queue>path[MAXSIZE];   //最大堆存每个点所能到达的行星据点的距离 
queuenode;    
void Spfa()   
{
	for(int i=1;i<=n;i++)
	{
		if(sign[i])   //只判断行星据点到其他点的最短距离 
		{
			for(int j=1;j<=n;j++) //初始化 
			{
				dist[j]=INFI;
				inq[j]=false;
			}
			dist[i]=0;
			node.push(i);      //将起点纳入队列中 
			inq[i]=true;
			while(!node.empty())  
			{
				int min_i=node.front();  //得到队列元素并出队 
				node.pop();   
				
				inq[min_i]=false;  //元素出队 
				int len=List[min_i].size();
				for(int j=0;jid;
					if(dist[t]>dist[min_i]+List[min_i][j]->W)
					{
						dist[t]=dist[min_i]+List[min_i][j]->W;
						if(!inq[t])    //把不在队列里的元素入队 
						{
							node.push(t);
							inq[t]=true;
						}
					}
						
				}
			} 
			
			for(int j=1;j<=n;j++)   //求出每个行星据点到其他所有点的最小距离时就将该距离添加到每个行星据点队列后面 
			{                        //并且只存储前k个，多于k个就将最大堆的堆顶元素拿出来 
				if(dist[j]!=INFI) 
				{
					if(path[j].size()dist[j]) 
						{
							path[j].pop();
							path[j].push(dist[j]);
						}
 					}
				}
			}
			
		}
	}
}
void Solve()    //输出每个据点队列的行星据点距离并求和 
{
	for(int i=1;i<=n;i++)
	{
		int sum=0;
		int j=0;
		while(!path[i].empty())
		{
			sum+=path[i].top();
		//	cout<>n>>m>>k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&sign[i]);   //读入据点类型 
	}
	for(int i=0;i>u>>v>>w;
		scanf("%d %d %d",&u,&v,&w);
		if(u==v) continue;
		Adj a=new AdjNode;  //无向图，两个顶点都要进行操作 
		a->id=v;
		a->W=w;
		List[u].push_back(a);
		Adj b=new AdjNode;
		b->id=u;
		b->W=w;
		List[v].push_back(b);
	}
	Spfa();
	Solve();
	return 0;
}

参考这篇100分的文章，我的思路跟他的几乎一样
317任务100分SPFA算法100分，参考这篇博文
https://blog.csdn.net/weixin_41297324/article/details/110733559