| ||||||||||
| 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