hdu6075 2019CCPC网络选拔赛1004 path

题意：给定一个带权有向图，有q组询问，每次询问在有向图的所有路径中，第k小的路径权值

解题思路：因为k最大只有5e4，考虑暴力搜索出前maxk小的路径并用数组记录权值，然后就可以O(1)查询。

具体实现：暴力搜索时可以借助Dijkstra最短路的思想，即用已知的最短路更新得出新的最短路。先将所有的边都装进一个multiset里面，然后每次将multiset里的首元素取出，作为新的答案，然后再用它来更新新的最短路，这样不断扩散的话就可以得到答案。

但是，这样可能会TLE或MLE，考虑再加加优化，首先我们只需要前maxk小的路径，所以multiset的可以限制在maxk以内，这样就不会MLE了，然后我们还可以先对每个节点的邻接表中的边按权值从小到大排序，这样在枚举的时候如果新路径的权值大于multiset中的最大值就可以直接break掉，这样就不会TLE了。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=5e4+5;

const int MAXK=5e4+5;

int n,m,q,k;

struct Edge{

	int id,u,v;

	ll w;

	bool operator<(const Edge& b)const{return w<b.w;}

}; 

multiset<Edge>s;

vector<Edge>G[maxn];

ll ans[MAXK];

int tot,maxk,qry[maxn];

void init(){

	for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());

	int cnt=0;

	while(true){

		//cout<<"S:\n";for(auto i:s)cout<<i.u<<" "<<i.v<<" "<<i.w<<"\n";

		ans[++cnt]=s.begin()->w;

		Edge e=*s.begin(),tmp;

		s.erase(s.begin());

		if(cnt>=maxk)break;

		int psz=(int)s.size();

		int sz=(int)G[e.v].size();

		if((int)s.size()+sz<=maxk){

			for(int i=0;i<sz;i++){

				Edge t=G[e.v][i];

				tmp.id=++tot;tmp.u=e.u;tmp.v=t.v;tmp.w=e.w+t.w;

				s.insert(tmp);

			}

		}

		else{

			for(int i=0;i<sz;i++){

				Edge t=G[e.v][i];

				if((int)s.size()<=maxk){

					tmp.id=++tot;tmp.u=e.u;tmp.v=t.v;tmp.w=e.w+t.w;

					s.insert(tmp);

				}

				else{

					Edge last=*(--s.end());

					if(last.w>e.w+t.w){

						s.erase(last);

						tmp.id=++tot;tmp.u=e.u;tmp.v=t.v;tmp.w=e.w+t.w;

						s.insert(tmp);

					}

					else break;

				}

			}

		}

	}

}

int main()

{

//#ifndef ONLINE_JUDGE

//	freopen("in.txt","r",stdin);

//#endif

	int T;

	scanf("%d",&T);

	while(T--){

		scanf("%d %d %d",&n,&m,&q);

		for(int i=1;i<=n;i++)G[i].clear();

		s.clear();tot=0;

		int u,v;

		ll w;

		Edge tmp;

		for(int i=1;i<=m;i++){

			scanf("%d %d %lld",&u,&v,&w);

			tmp.id=++tot;tmp.u=u;tmp.v=v;tmp.w=w;

			G[u].push_back(tmp);

			s.insert(tmp);

		}

		maxk=0;

		for(int i=1;i<=m;i++){

			scanf("%d",&qry[i]);

			maxk=max(maxk,qry[i]);

		}

		init();

		for(int i=1;i<=m;i++){

			printf("%lld\n",ans[qry[i]]);

		}

	}

    return 0;

}

巴特西

hdu6075 2019CCPC网络选拔赛1004 path

最新文章

热门文章