# include<iostream.h>
int vexNum,arcNum;
long weight[100];
int arcs[100][100];
int dis[100][100];//dis[v][w]表示v到w的最少权值
long result[100][100];
int k;
long sum;
#define maxValue 32767

void init()
{
    int i,j;
    for(i=0;i<vexNum;i++)
        cin>>weight[i];
    for(i=0;i<100;i++)
        for(j=0;j<100;j++){
            if(i==j)
                arcs[i][j]=0;
            else
                arcs[i][j]=maxValue;
        }
    int v1,v2,w;
    for(i=0;i<arcNum;i++)
    {
        cin>>v1>>v2>>w;
        arcs[v1-1][v2-1]=w;
        arcs[v2-1][v1-1]=w;
    }
}

void shortestPath_floyd()//求每个点间的最短路径
{
    int i;
    for(i=0;i<vexNum;i++)
        for(int j=0;j<vexNum;j++)
             dis[i][j]=arcs[i][j];
    for(int k=0;k<vexNum;k++)//循环嵌套顺序不能调换，这样才相当于BFS
    {
        for(i=0;i<vexNum;i++)
        {
            for(int j=0;j<vexNum;j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    //如果i，j中间有di那么必须是i，k中有di或者k，j中有di
                }
            }
        }
    }
}
void min()
{
    int i,j;
    k=0;
    long sum1=0;
    for(j=0;j<vexNum;j++)
    {
        result[0][j]=dis[0][j]*weight[j];
        sum1+=result[0][j];
    }
    sum=sum1;
    for(i=0;i<vexNum;i++)
    {
       sum1=0;
       for(j=0;j<vexNum;j++)
       {
           result[i][j]=dis[i][j]*weight[j];
           sum1+=result[i][j];
       }
       if(sum1<sum)
        {
            sum=sum1;
            k=i;
       }
    }
}


        

int main()
{
    while(cin>>vexNum>>arcNum)
    {

    init();
    shortestPath_floyd();

    min();
    cout<<k+1<<" "<<sum<<endl;
    }
    return 0;
}

评论