1 #include 
     
       2 #include
      
        3 #include
       
         4 #include 
        
          5 #include
         
           6 using namespace std; 7 int ll[1001][1001]; 8 struct node 9 {10     int per;11     int sumlen;12     bool vis;13     node() :per(0), sumlen(0),vis(0) {};14 };15 node dd[1001];16 int dijikstra(int s,int n)17 {18     int i,sum = 0,j, min,count=0;19     while (count < n-1)20     {21         min = 1 << 30;22         dd[s].vis = 1;//s为每次可能替换成的前驱23         for (i = 1; i <= n; i++)24         {25             if (ll[s][i]>0&& !dd[i].vis)//次节点的前驱可修改26             {27                 if (!dd[i].per)//没有前驱28                 {29                     dd[i].per = s;30                     dd[i].sumlen += ll[s][i]+dd[s].sumlen;31                 }32                 else//已有前驱 判断是否变动33                 {34                     if (dd[i].sumlen > dd[s].sumlen + ll[i][s])35                     {36                         dd[i].per = s;37                         dd[i].sumlen = dd[s].sumlen + ll[i][s];38                     }39                     else if (dd[i].sumlen == dd[s].sumlen + ll[i][s])//注意我们要求的是最短公路40                     {41                         if (ll[i][dd[i].per] > ll[i][s])42                         {43                             dd[i].per = s;44                             dd[i].sumlen = dd[s].sumlen + ll[i][s];45                         }46                     }47                 }48             }49             if (!dd[i].vis&&dd[i].sumlen&&min >=dd[i].sumlen)//min记录每次最短公路50             {51                 if (min == dd[i].sumlen)52                 {53                     if (ll[dd[j].per][j] > ll[dd[i].per][i])54                     {55                         min = dd[i].sumlen;56                         j = i;57                     }58                 }59                 else60                 {61                     min = dd[i].sumlen;62                     j = i;63                 }64             }65         }66         s = j;67         sum += ll[dd[j].per][j];68         count++;69     }70     return sum;71 }72 int main()73 {74     memset(ll,-1,sizeof(ll));75     int n, m; cin >> n >> m;76     //n = 4; m = 5;77     int i, a, b, c;78     for (i = 1; i <= n; i++)79         ll[i][i] = 0;80     for (i = 0; i < m; i++)81     {82         cin >> a >> b >> c;83         ll[a][b] = ll[b][a] = c;84     }85     /*ll[1][2] = ll[2][1] = 4;86     ll[1][3] = ll[3][1] = 5;87     ll[2][3] = ll[3][2] = 2;88     ll[2][4] = ll[4][2] = 3;89     ll[3][4] = ll[4][3] = 2;*/90     cout << dijikstra(1, n) << endl;91     return 0;92 }