这题我自己是用邻接矩阵+dijskstra方法来求的,第九个例子TLE。网上看了别人的代码,是用邻接表+BFS来完成。

这里可以学到两个小技巧,邻接表的表示方法和INT_MAX的表示方法。

 /*
 ID:yingzho1
 LANG:C++
 TASK:butter
 */
 #include<fstream>
 #include<cstring>
 #include<queue>
 #include <limits>
 using namespace std;

 ifstream fin("butter.in");
 ofstream fout("butter.out");

 ;

 struct vertex
 {
         int end,len;
 };
 vertex adj[MAX][MAX];

 }, cowpos[]={}, n, p, c;
 };
 int distances[MAX];

 int search(int start)
 {
         memset(pushed, , sizeof(pushed));
         ; k <= p; k++)
             distances[k] = numeric_limits<int>::max();

         queue<int> Q;
         Q.push(start);
         pushed[start] = true;
         distances[start] = ;
         while(!Q.empty())
         {
                 int x = Q.front();
                 Q.pop();
                 pushed[x] = false;
                 ; j < cnt[x]; j++)
                 {
                         if(distances[x]+adj[x][j].len < distances[adj[x][j].end])
                         {
                                 distances[adj[x][j].end] = distances[x]+adj[x][j].len;
                                 if(!pushed[adj[x][j].end])
                                 {
                                         Q.push(adj[x][j].end);
                                         pushed[adj[x][j].end] = true;
                                 }
                         }
                 }
         }

         ;

         ; i<=n; i++)
         {
                 ;
                 else  ans+=distances[cowpos[i]];
         }
         return ans;
 }

 int main()
 {
         memset(cnt, , sizeof(cnt));
         fin>>n>>p>>c;
         ; i<=n; i++)
                 fin>>cowpos[i];

         , s, t, value; i <= c; i++)
         {
                 fin>>s>>t>>value;
                 adj[s][cnt[s]].end = t; adj[s][cnt[s]].len = value; cnt[s]++;
                 adj[t][cnt[t]].end = s; adj[t][cnt[t]].len = value; cnt[t]++;
         }

         int res, mins = numeric_limits<int>::max();
         ; i <= p; i++)
         {
                 res = search(i);
                 ) mins  =  res;
         }

         fout<<mins<<endl;
         ;
 }
05-11 13:30