1690.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 93 行

#include <stdio.h>
#include <string.h>
#include <math.h>

__int64 ll1, ll2, ll3, ll4;
__int64 cc1, cc2, cc3, cc4;
__int64 length[110][110];
__int64 xray[110];
int n, m;

__int64 cost(__int64 w)
{
	if (w < 0)
	{
		w = -1 * w;
	}
	if (w == 0)
	{
		return 0;
	}
	else if (w <= ll1)
	{
		return cc1;
	}
	else if (w <= ll2)
	{
		return cc2;
	}
	else if (w <= ll3)
	{
		return cc3;
	}
	else if (w <= ll4)
	{
		return cc4;
	}
	return -1;
}

int main()
{
	int test, i, j, k, t = 0;
	scanf("%d", &test);
	while (test--)
	{
		memset(length, 0, sizeof(length));
		memset(xray, 0, sizeof(xray));
		scanf("%I64d %I64d %I64d %I64d", &ll1, &ll2, &ll3, &ll4);
		scanf("%I64d %I64d %I64d %I64d", &cc1, &cc2, &cc3, &cc4);
		scanf("%d%d", &n, &m);
		for (i = 1; i <= n; i++)
		{
			scanf("%I64d", &xray[i]);
		}
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				length[i][j] = cost(xray[i] - xray[j]);
			}
		}
		for (k = 1; k <= n; k++)
		{
			for (i = 1; i <= n; i++)
			{
				for (j = 1; j <= n; j++)
				{
					if (i != j && j != k && i != k)
					{
						if (length[i][k] != -1 && length[k][j] != -1 && ((length[i][j] != -1 && length[i][k] + length[k][j] < length[i][j]) || length[i][j] == -1))
						{
							length[i][j] = length[i][k] + length[k][j];
						}
					}
				}
			}
		}
		printf("Case %d:\n", ++t);
		for (k = 0; k < m; k++)
		{
			scanf("%d %d", &i, &j);
			if (length[i][j] == -1)
			{
				printf("Station %d and station %d are not attainable.\n", i, j);
			}
			else
			{
				printf("The minimum cost between station %d and station %d is %I64d.\n", i, j, length[i][j]);
			}
		}
	}
	return 0;
}