【USACO18DEC】Fine Dining

[USACO18DEC]Fine Dining#

Coo coo coo...

What? The previous exams?

...I'll make up for them when I have time (don't worry, you won't have time)

Problem#

After a long day, the hungry cows are ready to return to the barn. The farm consists of N pastures (2≤N≤50,000), conveniently numbered 1...N. All cows need to go to the barn located in pasture N. Each of the other N−1 pastures contains one cow. The cows can move between pastures using M undirected paths (1≤M≤100,000). The i-th path connects pastures ai and bi and takes time ti to traverse. Each cow can return to the barn by taking some paths.

Due to hunger, the cows are happy to stop and eat on their way home. There are K (1≤K≤N) delicious hay bales on the farm, with the i-th hay bale having a tastiness value of yi. Each cow wants to stop at one of the hay bales on her way back to the barn, but she will only do so if stopping at that hay bale does not increase her travel time back to the barn by more than the tastiness value of that hay bale. Note that a cow only "officially" stops at one hay bale on her path back to the barn, even if she passes other pastures with hay bales; she simply ignores the other hay bales.

Input and Output Format#

Input Format:
The first line of input contains three space-separated integers N, M, and K. The following M lines each contain three integers ai, bi, and ti, indicating that there is a path that takes ti time to traverse between pastures ai and bi (ai is not equal to bi, and ti is a positive integer not exceeding 10^4).
The following K lines describe the hay bales: each line contains two integers describing a pasture where a hay bale is located and its tastiness value (a positive integer not exceeding 10^9). There may be multiple hay bales in the same pasture.

Output Format:
Output N−1 lines. If the cow in pasture i can go to one of the hay bales on her way back to the barn and eat there, then the i-th line should be the integer 1; otherwise, it should be the integer 0.

Input and Output Examples#

Input Example #1:

Output Example #1:

1
1
1

Explanation#

In this example, the cow in pasture 3 can stop and eat because her travel time back to the barn will only increase by 6 (from 2 to 8), which is not greater than the tastiness value of the hay bale, 7. The cow in pasture 2 can obviously eat the hay in pasture 2 because it does not change her optimal path. For the cow in pasture 1, it is an interesting case because it seems that her optimal path (10) may have a large increase due to stopping for food. However, there is indeed a path that allows her to stop at the hay bale: go to pasture 4, then go to pasture 2 (eat hay), and then return to pasture 4.

Approach#

The expert tells us to first run SPFA on the original graph to obtain the shortest distance from each node to n, and store it in d2.
Store the tastiness values in the array a.
Then, create a directed edge from n + 1 to the pastures with hay bales, with the edge weight being d2[i] - a[i].
Next, run SPFA again with n + 1 as the source node and store the distances in d1.
Finally, check if d1[i] is less than or equal to d2[i].
The idea behind this is that a cow will walk to a hay bale and then take the shortest path to n, so we can directly connect d2[i] - a[i] to n + 1 and find the shortest path to compare d[i] with the difference in distance if the cow takes a detour.

Code#

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 100005;
struct ed {
    int to, nex, w;
} e[MAXN * 3];;
int head[MAXN], a[MAXN], plc[MAXN], d1[MAXN], d2[MAXN];
int newp;
bool v[MAXN];
int n, m, k;

void insert(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}
#include<queue>
void spfa(int p) {
    queue<int> q;
    q.push(p);
    memset(v, 0, sizeof(v));
    memset(d1, 0x3f, sizeof(d1));
    //v[p] = 1;
    d1[p] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        v[u] = 0;
        for (int i = head[u]; i; i = e[i].nex) {
            int y = e[i].to;
            if (d1[y] > d1[u] + e[i].w) {
                d1[y] = d1[u] + e[i].w;
                if (!v[y]) {
                    v[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}

int main (void) {
//    freopen("dining.in", "r", stdin);
//    freopen("dining.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= m; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        insert(p1, p2, w);
        insert(p2, p1, w);
    }

    spfa(n);
    for (int i = 1; i <= n; ++i) {
        d2[i] = d1[i];
    }

    for (int i = 1; i <= k; ++i) {
        scanf("%d", plc + i);
        scanf("%d", a + i);
        insert(n + 1, plc[i], d2[plc[i]] - a[i]);
    }
    spfa(n + 1);

    for (int i = 1; i < n; ++i) {
        if (d1[i] <= d2[i]) {
            printf("1\n");
        }
        else printf("0\n");
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}