接力
【问题描述】
接力共有n名队员（编号1-n）参加，在同一时刻赛道上允许有任意多名选手同时赛跑。比赛开始前，所有交警在起跑线等待起跑。
在t=0时刻，编号为1的选手开始赛跑，L1秒后跑完一圈回到起点。当选手i跑完一圈他会示意Mi名选手开始接力。（选手可能被多次示意，只算最早的示意）每个选手只跑一圈。
接力的总时间为最后一个选手结束赛跑的时间。求接力的总时间。
【输入格式】
第一行一个单独的整数n，表示有n名选手。
接下来n行，每行开始有2个整数Li，Mi，接下来有Mi个整数，表示示意选手的编号。
【输出格式】
一行一个整数，表示接力的总时间。
【输入样例】
5
4 2 2 4
3 3 1 3 4
7 1 5
4 2 3 5
1 0
【输出样例】
14
【数据范围与约定】
对于30%的数据：n <= 10。
对于60%的数据：n <= 300。
对于100%的数据：n <= 1000。
这题没啥话说，每个选手就是最早接到信号时开始跑，那就是起点到他的最短时间，所以只要从起点做一遍最短路，其总时间就是选手开始跑的最早时间（就是最短路）加上其跑步时间的最大值。至于最短路本人用的时spfa算法
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct sd
{
int begin, end, val;
int Next, Num;
}map[800100];
int dui[400000], num, maxx = 0;
int dis_Home[1010], mask[1010], start[1010];
void SPFA(int op)
{
int head = 1, tail = 1;
dui[1] = op;
mask[op] = 1;
dis_Home[op] = 0;
while (head >= tail)
{
int now = start[dui[tail]];
while (now)
{
long long far = dis_Home[dui[tail]] + map[now].val;
if (far < dis_Home[map[now].end])
{
dis_Home[map[now].end] = far;
if (!mask[map[now].end])
{
dui[++head] = map[now].end;
mask[map[now].end] = 1;
}
}
now = map[now].Next;
}
mask[dui[tail++]] = 0;
}
}
int v[1010];
int main(void)
{
freopen("relay.in","r",stdin);
freopen("relay.out","w",stdout);
int i, j, n;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
int m;
scanf("%d%d", &v[i], &m);
for (j = 1; j <= m; j++)
{
int s;
scanf("%d", &s);
map[++num].begin = i; map[num].end = s;
map[num].val = v[i]; map[num].Next = start[i];
start[i] = num;
}
dis_Home[i] = 2000000000;
}
SPFA(1);
for (i = 1; i <= n; i++) maxx = maxx < dis_Home[i] + v[i] && dis_Home[i] != 2000000000 ? dis_Home[i] + v[i]: maxx;
printf("%d", maxx);
fclose(stdin);
fclose(stdout);
return 0;
}
/*#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int s[1010][1010], m[1010],v[1010];
int ds[120000][500];
int mask[1010];
int main(void)
{
int i, j, n;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d%d", &v[i], &m[i]);
for (j = 1; j <= m[i]; j++)
{
scanf("%d", &s[i][j]);
}
}
ds[0][1] = ds[0][0] =1;
int zhi = 0, tail = 0;
int ans = 0;
while (zhi <= tail)
{
while (ds[zhi][0] == 0) zhi++;
for (i = 1; i <= ds[zhi][0]; i++)
{
if (mask[ds[zhi][i]]) continue;
mask[ds[zhi][i]] = 1;
for (j = 1; j <= m[ds[zhi][i]]; j++)
{
int boom = 1;
if (!mask[s[ds[zhi][i]][j]])
{
boom = 0;
ds[zhi+v[ds[zhi][i]]][++ds[zhi+v[ds[zhi][i]]][0]] = s[ds[zhi][i]][j];
tail = max(tail, zhi+v[ds[zhi][i]]);
}
if (boom) ans = max(ans, zhi+v[ds[zhi][i]]);
}
}
zhi++;
}
printf("%d", tail);
}*/