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 671superone at 2012-05-05 07:25:06 on Problem 3411
先贴一下代码,大牛们注意看打注释的部分
#include <iostream>
#include <vector>
using namespace std;

#define maxn		11
#define inf			0x3f3f3f3f
#define max(a,b)	((a)>(b)?(a):(b))
#define min(a,b)	((a)<(b)?(a):(b))

struct Pay
{
	int node, did, didnot;
};
vector<Pay> pay[maxn][maxn];
bool map[maxn][maxn];
int vis[maxn];
int n, m, maxlen, money;

void init()
{
	int i, j;
	for (i=1; i<=n; i++)
	{
		for (j=1; j<=n; j++)
		{
			pay[i][j].clear();
		}
	}
	maxlen = inf;
	memset(map, 0, sizeof(map));
	memset(vis, 0, sizeof(vis));
}

void dfs(int k,int mon)
{
	if (k == n)
	{
		maxlen = min(maxlen, mon);
		return ;
	}
	int i;
	for (i=1; i<=n; i++)
	{
		if (map[k][i] && vis[i]<3)/*这里,原本我弄得是2,但是wa,后来仔细想了想,弄成3,于是A了,但是后来又找了一组测试数据,符合输入条件,但是结果却是错的。数据在下面*/
		{
			int minm = inf;
			int j;
			for (j=0; j<pay[k][i].size(); j++)
			{
				if (vis[pay[k][i][j].node])
				{
					minm = min(minm, pay[k][i][j].did);
				}
				else
				{
					minm = min(minm, pay[k][i][j].didnot);
				}
			}
			vis[i]++;
			dfs(i, mon+minm);
			vis[i]--;
		}
	}
}

int main()
{
	while (scanf("%d %d",&n, &m) != EOF)
	{
		init();
		for (int i=0; i<m; i++)
		{
			int a, b;
			Pay p;
			scanf("%d %d %d %d %d", &a, &b, &p.node, &p.did, &p.didnot);
			map[a][b] = 1;
			pay[a][b].push_back(p);
		}
		vis[1]++;
		dfs(1, 0);
		if (maxlen == inf)
		{
			puts("impossible");
		}
		else
		{
			printf("%d\n", maxlen);
		}
	}
	return 0;
}
测试数据:

8 10
1 2 1 10 100
1 3 1 10 100
1 4 1 10 100
1 7 1 10 100
2 1 2 10 100
4 1 2 10 100
7 1 2 10 100
3 5 2 12 10000
5 6 4 13 10000
6 8 7 14 10000


本来结果  109,但实际结果10075,原因就是,有时候需要访问一个点4次甚至5次才可以通过。。。但是这道题,访问3次就可以A掉
把上面的3才成4,就完全正确

奇怪的是。。。。4居然是0MS~~~3居然需要16MS!!!
10155514	671superone	3411	Accepted	180K	0MS	C++	1378B	2012-05-05 07:23:33
10153154	671superone	3411	Accepted	180K	16MS	C++	1378B	2012-05-04 17:17:29

希望大家看了能有所帮助!

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