Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

纪念第一次自己构思,第一次自己构图,一次AC

Posted by exmorning at 2011-02-07 23:19:04 on Problem 1161
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator