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

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;
int n;
int w[MAXN];
int g[MAXN][MAXN];
int x,y,z;
int num[MAXN];
bool vis[MAXN];
void d(){
    for(int i=1;i<=n;i++){
        int minx=1e9;
        int k=0;
        for(int j=0;j<n;j++){
            if(w[j]<minx&&!vis[j]){
                minx=w[j];
                k=j;
            }
        }
        vis[k]=true;
        for(int j=0;j<n;j++){
            if(g[k][j]!=-1&&vis[j]){
                int a=g[k][j];
                if(w[k]+w[j]<w[a]){
                    w[a]=w[k]+w[j];
                    num[a]=num[k]*num[j];
                }else if(w[k]+w[j]==w[a]){
                    num[a]+=num[k]*num[j];
                }
            }
        } 
    }
}
int main(){
    freopen("msyrup.in","r",stdin);
    freopen("msyrup.out","w",stdout);
    memset(g,-1,sizeof(g));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>w[i];
        num[i]=1;
    }
    while(cin>>x>>y>>z){
        g[x][y]=g[y][x]=z;
    }
    d();
    cout<<w[0]<<' '<<num[0]<<endl;
    return 0;
}