HDU - 6705 path

path

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2608 Accepted Submission(s): 625

Problem Description
You have a directed weighted graph with n vertexes and m edges. The value of a path is the sum of the weight of the edges you passed. Note that you can pass any edge any times and every time you pass it you will gain the weight.

Now there are q queries that you need to answer. Each of the queries is about the k-th minimum value of all the paths.

Input
The input consists of multiple test cases, starting with an integer t (1≤t≤100), denoting the number of the test cases.
The first line of each test case contains three positive integers n,m,q. (1≤n,m,q≤5∗104)

Each of the next m lines contains three integers ui,vi,wi, indicating that the i−th edge is from ui to vi and weighted wi.(1≤ui,vi≤n,1≤wi≤109)

Each of the next q lines contains one integer k as mentioned above.(1≤k≤5∗104)

It’s guaranteed that Σn ,Σm, Σq,Σmax(k)≤2.5∗105 and max(k) won’t exceed the number of paths in the graph.

Output
For each query, print one integer indicates the answer in line.

Sample Input
1
2 2 2
1 2 1
2 1 2
3
4

Sample Output
3
3
Hint

1->2 value :1

2->1 value: 2

1-> 2-> 1 value: 3

2-> 1-> 2 value: 3

肯定不能每次都把出点相邻的边，加进堆里面，因为边可能很多。我们用A*的思想去想这个第k大的问题，其实我们每次只需要把当前从堆中取出来的边的出点连接的最小的权值边和这条边的下一条边放进堆里面即可。

可以反证得到。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int T,n,m,Q,mx,a[N],vis[N],cnt;
vector<pair<int,int> > g[N];
struct node{
	int u,v,w,id;
};
bool operator < (node a,node b){
	return a.w>b.w;
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%lld %lld %lld",&n,&m,&Q);
		for(int i=1;i<=n;i++)	g[i].clear(); mx=cnt=0;
		while(m--){
			int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);	g[a].push_back({c,b});
		}
		for(int i=1;i<=n;i++)	sort(g[i].begin(),g[i].end());
		priority_queue<node> q;
		for(int i=1;i<=Q;i++)	scanf("%lld",&a[i]),mx=max(mx,a[i]);
		for(int i=1;i<=n;i++)	
			if(g[i].size())	q.push({i,g[i][0].second,g[i][0].first,0});
		while(cnt<mx&&q.size()){
			int u=q.top().u,v=q.top().v,w=q.top().w,id=q.top().id;	q.pop();
			id++;	vis[++cnt]=w;
			if(id<g[u].size())	
				q.push({u,g[u][id].second,g[u][id].first+w-g[u][id-1].first,id});
			if(g[v].size())	q.push({v,g[v][0].second,g[v][0].first+w,0});
		}
		for(int i=1;i<=Q;i++)	printf("%lld\n",vis[a[i]]);
	}
	return 0;
}