Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
纪念第一次自己构思,第一次自己构图,一次AC#include<iostream> #include<algorithm> using namespace std; #define INF 10000000 typedef struct { int t[210]; }t2r; t2r t2rs[260]; int n, m, l, e[210][210], map[260][260], members[40], wall[210], minAll; void Init() { int i, j, vs; minAll = INF; memset(map, 0, sizeof(map)); cin>>m>>n>>l; for(i = 0; i <= n; i++) t2rs[i].t[0] = 0; for(i = 0; i <= m; i++) for(j = 0; j <= m; j++) if(i == j) e[i][j] = 0; else e[i][j] = INF; for(i = 1; i <= l; i++) cin>>members[i]; for(i = 1; i <= m; i++) { cin>>vs; for(j = 1; j <= vs; j++) { cin>>wall[j]; t2rs[wall[j]].t[++t2rs[wall[j]].t[0]] = i; } for(j = 1; j < vs; j++) { if(!map[wall[j]][wall[j + 1]]) { map[wall[j]][wall[j + 1]] = map[wall[j + 1]][wall[j]] = i; } else { e[i][map[wall[j]][wall[j + 1]]] = e[map[wall[j]][wall[j + 1]]][i] = 1; } } if(!map[wall[vs]][wall[1]]) { map[wall[vs]][wall[1]] = map[wall[1]][wall[vs]] = i; } else { e[i][map[wall[vs]][wall[1]]] = e[map[wall[1]][wall[vs]]][i] = 1; } } } void Floyd() { int i, j, k; for(k = 1; k <= m; k++) for(i = 1; i <= m; i++) for(j = 1; j <= m; j++) { if(e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j]; } } void Enumerate() { int i, j, k, min, sum; for(k = 1; k <= m; k++) { sum = 0; for(i = 1; i <= l; i++) { min = INF; for(j = 1; j <= t2rs[members[i]].t[0]; j++) { if(min > e[t2rs[members[i]].t[j]][k]) min = e[t2rs[members[i]].t[j]][k]; } sum += min; } if(sum < minAll) minAll = sum; } } void Print() { cout<<minAll<<endl; } int main() { Init(); Floyd(); Enumerate(); Print(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator