佳佳的魔法药水

37pt WA

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int ans[1000100];
int dis[1000100];
bool inq[1000100];
struct ede{
	int v,w;
};
vector<ede> g[100100];
vector<int> e[100100];
int c[10010];
void spfa(){
	queue<int> q;
	//memset(dis,0x3f,sizeof(dis));
	for(int i = 0;i < n;i++){
		dis[i] = c[i];
		ans[i] = 1;
		q.push(i);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(ede vis: g[u]){
			int a = vis.v,b = vis.w;
			if(dis[a] + dis[b] < dis[u]){
				ans[u] = ans[a]*ans[b];
				dis[u] = dis[a]+dis[b];
				for(int vv:e[u]){
					if(!inq[vv]){
						inq[vv] = 1;
						q.push(vv);
					}
				}
			}
			else if(dis[a]+dis[b] == dis[u]){
				ans[u] += ans[a]*ans[b];
			}
		}
	}
}
int tot;
signed main(){
	cin>>n;
	for(int i = 0;i < n;i++){
		cin>>c[i];
	}
	int u,v,w;
	while(cin>>u>>v>>w){
		g[w].push_back({u,v});
		e[u].push_back(w);
		e[v].push_back({w});
	}
	spfa();
	cout<<dis[0]<<" "<<ans[0]<<endl;
	return 0;
}