hdu5695 拓扑排序 优先队列优化

题目链接hdu5695
！ans会爆int

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
vector<int> s[maxn];
int ind[maxn],vis[maxn];
int n,m;
void init(){
	memset(ind,0,sizeof(ind));
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=n;i++)
		s[i].clear();
}
void toop(){
	ll ans=0;
	ll minn=inf;
	priority_queue< int, vector< int >,less<int> >q;
	for(int i=1;i<=n;i++){
		if(ind[i]==0){
			q.push(i);
			vis[i]=1;
		} 
	}
	while(q.size() ){
		ll u=q.top();
		q.pop();
		minn=min( minn,u);
		ans+=minn;
		for(int i=0;i<s[u].size();i++){
			int v=s[u][i];
			ind[v]--;
			if(ind[v]==0&&!vis[v]) {
				q.push(v);
				vis[v]=1;
			}
		}
	}
	printf("%lld\n",ans);
}



int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			ind[b]++;
			s[a].push_back(b);
		}
		toop();
	}
	return 0;
}