记录编号	597395	评测结果	AAAAAAAAAA
题目名称	魔法药水	最终得分	100
用户昵称	黄天宇	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2024-11-27 14:55:12	内存使用	7.21 MiB

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int n;
long long v[MAXN];
long long dis[MAXN];
long long num[MAXN];
bool b[MAXN];
bool vis[MAXN];
int mapp[MAXN][MAXN];
int cnt;
bool bo;
int p;
long long sum[MAXN];
int main(){
	freopen("msyrup.in","r",stdin);
	freopen("msyrup.out","w",stdout);
	cin>>n;
	memset(mapp,-1,sizeof(mapp));
	for(int i=0;i<n;i++){
		cin>>dis[i];
		sum[i]=1;
	}
	int x,y,z;
	while(cin>>x>>y>>z){
		mapp[x][y]=z;
		mapp[y][x]=z;
	}
	for(int i=0;i<n;i++){
		long long minx=1e18;
		p=0;
		for(int j=0;j<n;j++){
			if(!b[j]&&minx>dis[j]){//最小的点，即不会被更新的点 
				p=j;
				minx=dis[j];
			}
		}
		b[p]=1;
		for(int j=0;j<n;j++){
			if(b[j]&&mapp[p][j]!=-1){
				if(dis[j]+dis[p]==dis[mapp[j][p]]){
					sum[mapp[j][p]]+=sum[j]*sum[p];
				}else
				if(dis[j]+dis[p]<dis[mapp[j][p]]){
					dis[mapp[j][p]]=dis[j]+dis[p];
					sum[mapp[j][p]]=sum[j]*sum[p];
				}
			}
		}
		
	}
	cout<<dis[0]<<" ";
	cout<<sum[0]<<endl;
	return 0;
}