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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴个DP规范c++代码

Posted by a280920481 at 2018-11-26 22:38:03 on Problem 2686
#include <iostream>
using namespace std;

struct Edge
{
	int to;
	int distance;
}G[31][30];//用于构建图的邻接表

int GSize[31];//图中每个节点的度

double d[256][31];//记录 [已使用的车票的集合][当前节点] 的状态节点的最小距离

int main()
{
	int n, m, p, a, b;//车票数 节点数 边数 起点 终点
	int ticket[8];//每个车票的马匹数

	int xi, yi, zi;//用于输入数据时的临时变量
	int intans;//用于输出保留3位小数点的结果的变量
	double ans;//用于记录最终答案的变量

	while (true)//案例循环
	{
		cin >> n >> m >> p >> a >> b;
		if (!n)
		{
			break;
		}

		//进行初始化
		ans = 1 << 30;//先将答案初始化为较大的数
		for (int i = 0; i <= m; i++)
		{
			for (int j = 0; j < (1 << n); j++)
			{
				d[j][i] = 1 << 30;//将每个节点的距离初始化为较大的数
			}
			GSize[i] = 0;
		}

		//进行数据输入
		for (int i = 0; i < n; i++)
		{
			cin >> ticket[i];
		}

		for (int i = 0; i < p; i++)
		{
			cin >> xi >> yi >> zi;

			G[xi][GSize[xi]].to = yi;
			G[xi][GSize[xi]].distance = zi;
			GSize[xi]++;

			G[yi][GSize[yi]].to = xi;
			G[yi][GSize[yi]].distance = zi;
			GSize[yi]++;
		}

		d[0][a] = 0;//将 [已使用的车票的集合为空集][当前节点为起始节点] 的状态节点的距离设为 0

		for (int U = 0; U < 1 << n; U++)
		{
			for (int i = 1; i <= m; i++)
			{
				for (int j = 0; j < GSize[i]; j++)
				{
					for (int k = 0; k < n; k++)
					{
						if (!((U >> k) & 1))
						{
							if (d[U | (1 << k)][G[i][j].to] > d[U][i] + (double)G[i][j].distance / ticket[k])
							{
								d[U | (1 << k)][G[i][j].to] = d[U][i] + (double)G[i][j].distance / ticket[k];
							}
						}
					}
				}
			}
		}

		
		for (int i = 0; i < (1 << n); i++)//对每个 当前节点为终点 的状态节点进行检索
		{
			if (d[i][b] < ans)
			{
				ans = d[i][b];
			}
		}

		//输出结果
		if (ans < (1 << 30))
		{
			ans = ans * 1000 + 0.5;
			intans = (int)ans;
			cout << intans / 1000 << '.';
			cout << (intans % 1000) / 100;
			cout << (intans % 100) / 10;
			cout << intans % 10 << '\n';
		}
		else
		{
			cout << "Impossible\n";
		}
	}

	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