这题我自己是用邻接矩阵+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; ; }