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

笨办法

Posted by ayxg at 2012-02-26 21:12:31 on Problem 1125
#include <stdio.h>

#define MAX 100
#define INF 0x0fffffff

int d[MAX + 1][MAX + 1];

int main()
{
	int st_n, t, k, s, pair, id, dur, min, tmp, stat;

	while (1)
	{
		scanf("%d", &st_n);
		if (st_n == 0)
			break;

		for (t = 1; t <= st_n; ++t)	
			for (k = 1; k <= st_n; ++k)
			{
				d[t][k] = INF;
			}

		for (t = 1; t <= st_n; ++t)
			d[t][t] = 0;

		for (t = 1; t <= st_n; ++t)
		{
			scanf("%d", &pair);	
			for (k = 0; k < pair; ++k)
			{
				scanf("%d%d", &id, &dur);
				d[t][id] = dur;
			}
		}
		
		stat = 1;
		while (stat)
		{
			stat = 0;
			for (t = 1; t <= st_n; ++t) 
			{
				for (k = 1; k <= st_n; ++k)
				{
					if (t != k)
					{
						for (s = 1; s <= st_n; ++s)
						{
							tmp = d[t][s] + d[s][k];
							if (tmp < d[t][k])
							{
								d[t][k] = tmp;
								stat = 1;
							}
						}
					}
				}
			}
		}

		min = INF;
		for (t = 1; t <= st_n; ++t)
		{
			tmp = 0;
			for (k = 1; k <= st_n; ++k)
			{
				if (d[t][k] > tmp)
					tmp = d[t][k];	
			}
			
			if (tmp < min)
			{
				min = tmp;
				id = t;
			}
		}

		if (min == INF)
			printf("disjoint\n");
		else
			printf("%d %d\n", id, min);
	}

	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