hdu 1690 Bus System floyd 模板

缘起

floyd板子

分析

1
2
3
由于中国人口众多，公共交通非常重要。 公交车是传统公交系统中重要的交通方式。 它现在仍然扮演着重要的角色。
X市的公交系统很奇怪。 与其他城市的系统不同，票价是根据两个车站之间的距离计算的。 这是一个描述距离和成本
之间关系的列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
你的邻居是一个非常吝啬的人。 他请你帮他计算他列出的两个站之间的最低费用。 你能帮他解决这个问题吗？
为简化此问题，您可以假设所有工作站都位于一条直线上。 我们使用x坐标来描述台站的位置。

【输入】
多样例，首先第一行是样例数目t（<=20）.每个样例首先第一行是8个数字 L1, L2, L3, L4, C1, C2, C3, C4
每个数字在[0,1e9]内. 而且L1<=L2<=L3<=L4.
然后是两个正整数 n（2<=N<=100）和m（0<=M<=500）, 表示n个站台和m次询问. 然后是n行，每行一个数字表示第i个站台的x坐标（在[-1e9,1e9]内）而且互不相同. 然后是m行，
每行2个数字，分别表示起点和终点.所有的询问起点!=终点. 

【输出】
对每个询问，如果可达，则输出最小cost, 否则输出"Station X and station Y are not attainable."

【样例输入】
2
1 2 3 4 1 3 5 7
4 2
1
2
3
4
1 4
4 1
1 2 3 4 1 3 5 7
4 1
1
2
3
10
1 4

【样例输出】
Case 1:
The minimum cost between station 1 and station 4 is 3.
The minimum cost between station 4 and station 1 is 3.
Case 2:
Station 1 and station 4 are not attainable.

【来源】
2008 “Sunline Cup” National Invitational Contest

floyd裸题. 唯一需要注意的是本题数据比较大，需要使用 __int64（hdu貌似不支持long long）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
typedef __int64 LL;
const LL inf = 1LL<<60; // 因为本题数据比较大, 所以inf不能取常规的 0x3f3f3f3f, 而且注意这里是 1LL<<60 不能写成1<<60L,后者是0， WA了两发~ 囧

LL g[105][105], L1, L2, L3, L4, C1, C2, C3, C4,n,m, x[105];

LL cost(LL i, LL j) // 根据表计算 i到达j的票价
{
	LL d = x[i]>x[j]?x[i]-x[j]:x[j]-x[i];
	if (!d)
	{
		return 0;
	}
	if (d<=L1)
	{
		return C1;
	}
	if (d<=L2)
	{
		return C2;
	}
	if (d<=L3)
	{
		return C3;
	}
	if (d<=L4)
	{
		return C4;
	}
	return inf;
}

void floyd()
{
	for (LL k = 1; k<=n;k++)
	{
		for (LL i = 1; i<=n; i++)
		{
			for (LL j = 1; j<=n; j++)
			{
				if (g[i][j]>g[i][k]+g[k][j])
				{
					g[i][j] = g[i][k]+g[k][j];
				}
			}
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	LL t;
	scanf("%I64d", &t);
	for (LL i = 1; i<=t; i++)
	{
		printf("Case %I64d:\n", i);
		scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &L1, &L2, &L3, &L4, &C1, &C2, &C3, &C4);
		scanf("%I64d%I64d", &n,&m);
		for (LL i = 1; i<=n; i++) scanf("%I64d", x+i);
		for (LL i = 1; i<=n; i++)
		{
			for (LL j = 1; j<=n;j++)
			{
				g[i][j] = cost(i,j);
			}
		} // floyd初始化
		floyd(); // 运行floyd
		while (m--) // 开始回答问题
		{
			LL u,v;
			scanf("%I64d%I64d", &u, &v);
			if (g[u][v] == inf)
			{
				printf("Station %I64d and station %I64d are not attainable.\n", u, v);
			}
			else
			{
				printf("The minimum cost between station %I64d and station %I64d is %I64d.\n",u, v, g[u][v]);
			}
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 1300kB
Length 1497
Lang G++
Submitted 2019-08-22 20:19:02
Shared
RemoteRunId 30394220