7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

接力

【问题描述】

接力共有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算法


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
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<cstdio>
#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);
}*/

 这题下面注释掉的是我tmd打优先队列时打的程序,刚开始打了最短路,后来不知道脑子抽了还是咋的改成优先队列,整整打了一个半小时没打出来。然后花了十多分钟打了最短路过了。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注