记录编号	41712	评测结果	AAATTTTTTT
题目名称	[WZOI 2011 S3] 周年纪念日	最终得分	30
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	7.124 s
提交时间	2012-08-09 16:49:23	内存使用	6.80 MiB

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
const int MAXN=100100;
const int MAXM=200200;
const int INF=(~0u)>>2;
const LL LINF=(1LL)<<62;
int N,M,P[MAXN];
LL ans,res,place;
class Edge{public:int u,v,c;}E[MAXM];
vector<int> map[MAXN],val[MAXN];
bool cmp(const Edge&a,const Edge&b)
{
	return a.c<b.c;
}

inline void init()
{
	scanf("%d%d\n",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%d",&P[i]);
	for(int i=1;i<=M;i++)
		scanf("%d%d%d\n",&E[i].u,&E[i].v,&E[i].c);
	sort(E+1,E+1+M,cmp);
}

int num[MAXN];
inline void merge(int a,int b){num[b]=a;}
int find(int k){return ((k==num[k])?k:(num[k]=find(num[k])));}

inline void mst()
{
	for(int i=1;i<=N;i++) num[i]=i;
	int now=0,x,y;ans=0;
	for(int i=1;i<=M;i++)
	{
		x=find(E[i].u);
		y=find(E[i].v);
		if(x==y) continue;
		merge(x,y); now++;
		ans+=E[i].c;
		map[E[i].u].push_back(E[i].v);
		map[E[i].v].push_back(E[i].u);
		val[E[i].u].push_back(E[i].c);
		val[E[i].v].push_back(E[i].c);
		if(now==N-1) 
		{
			printf("%lld %d\n",ans,E[i].c);
			break;
		}
	}
}

int flag[MAXN];
LL dist[MAXN];
 
void dfs(int k)
{
	for(unsigned int i=0;i<map[k].size();i++)
	{
		if(flag[map[k][i]]) continue;
		int v=map[k][i];
		flag[v]=1; dist[v]=dist[k]+val[k][i];
		res+=P[v]*dist[v]; dfs(v);
	}
}

inline void findpoint()
{
	ans=LINF;
	for(int i=1;i<=N;i++)
	{
		res=0;for(int j=1;j<=N;j++) dist[j]=INF;
		memset(flag,0,sizeof(flag));
		dist[i]=0; flag[i]=1; dfs(i);
		if(res<ans) ans=res,place=i;
	}
	printf("%lld %lld\n",place,ans);
}

int main()
{
	freopen("anniversary.in","r",stdin);
	freopen("anniversary.out","w",stdout);
	init();
	mst();
	findpoint();
	return 0;
}