BZOJ 5486 Fine Dining

发表于 更新于 本文字数： 2.7k 阅读时长 ≈ 5 分钟

传送门：BZOJ 5486 Fine Dining

Problem

Description

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。农场由 N 片牧场组成（2≤N≤50,000），方便起见编号为 1…

N。所有奶牛都要前往位于牧场 N 的牛棚。其他 N-1 片牧场中每片有一头奶牛。奶牛们可以通过 M 条无向的小路在牧场之间移动（1≤M≤100,000）。第 i 条小路连接牧场 ai 和 bi，通过需要时间 ti。每头奶牛都可以经过一些小路回到牛棚。由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 K 个有美味的干草捆，第 i 个干草捆的美味值为 yi。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅 “正式地” 在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

Input

第一行包含三个空格分隔的整数 N，M 和 K。

以下 M 行每行包含三个整数 ai，bi 和 ti，表示牧场 ai 和 bi 之间有一条需要 ti 时间通过的小路

（ai 不等于 bi，ti 为不超过 104 的正整数）。

以下 K 行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过 10^9 的正整数）。

同一片牧场中可能会有多个干草捆。

Output

输出包含 N-1 行。

如果牧场 i 里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第 i 行为一个整数 1，否则为一个整数 0

Sample Input

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

Sample Output

1
1
1
在这个例子中，牧场 3 里的奶牛可以停留进食，因为她回去的时间仅会增加 6（从 2 增加到 8），而这个增加量并没有
超过干草捆的美味值 7。牧场 2 里的奶牛显然可以吃掉牧场 2 里的干草，因为这并不会导致她的最佳路径发生变化。
对于牧场 1 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（10）可能会因为前去进食而有过大的增加量。
然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 4，然后去牧场 2（吃草），然后回到牧场 4。

Solution

Idea

分层图最短路。两种状态，吃或未吃干草。$dis [i] [0]$ 表示未吃干草状态下到达 i 的最短时间，$dis [i][1]$ 则为吃干草状态下到达 i 的最短时间。

将牧场之间的距离看做为正，将干草看为负。如果 $dis [n][1] <= dis [n][0]$ ，则输出 1.

Code

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
#define MAXN 50050
#define MAXM 200050
#define INF 0x3f3f3f3f
typedef long long LL;

using namespace std;

int n, m, k;

struct ed
{
    int to, next, cost;
}edge[MAXM];

int tot;
int head[MAXN];
int has[MAXN], dis[MAXN][2];
bool vis[MAXN];

void addedge(int u, int v, int w)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].cost = w;
    head[u] = tot++;
}

void spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[n][0] = 0;
    queue<int> que;
    que.push(n);
    while(!que.empty())
    {
        int u = que.front();
        int v;
        que.pop();
        vis[u] = false;

        for(int i = head[u]; ~i; i = edge[i].next)
        {
            v = edge[i].to;
            if(dis[u][0] + edge[i].cost < dis[v][0])
            {
                dis[v][0] = dis[u][0] + edge[i].cost;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }

            if(has[v] && dis[u][0] + edge[i].cost - has[v] < dis[v][1])
            {
                dis[v][1] = dis[u][0] + edge[i].cost - has[v];
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }

            if(dis[u][1] + edge[i].cost < dis[v][1])
            {
                dis[v][1] = dis[u][1] + edge[i].cost;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main()
{
    tot = 0;
    memset(head, -1, sizeof(head));

    scanf("%d%d%d", &n, &m, &k);
    int u, v, w;

    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for(int i=0; i<k; i++)
    {
        scanf("%d%d", &u, &w);
        has[u] = max(has[u], w);
    }

    if(has[n])
    {
        for(int i=1; i<n; i++)
            puts("1");
        return 0;
    }
    spfa();
    for(int i=1; i<=n-1; i++)
    {
        if(dis[i][0] >= dis[i][1])
            puts("1");
        else
            puts("0");
    }

    return 0;
}