# 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; }

评论