【USACO18DEC】美食佳餚

【USACO18DEC】Fine Dining#

咕咕咕。。。

什麼？前幾次考試？

。。。有空就補（放心你沒空的）

題目#

漫長的一天結束了，飢餓交加的奶牛們準備返回牛棚。農場由 N 片牧場組成（2≤N≤50,000），方便起見編號為 1…N。所有奶牛都要前往位於牧場 N 的牛棚。其他 N-1 片牧場中每片有一頭奶牛。奶牛們可以通過 M 條無向的小路在牧場之間移動（1≤M≤100,000）。第 i 條小路連接牧場 ai 和 bi，通過需要時間 ti。每頭奶牛都可以經過一些小路回到牛棚。

由於飢餓，奶牛們很樂於在他們回家的路上停留一段時間覓食。農場裡有 K（1<=K<=N）個有美味的乾草捆，第 i 個乾草捆的美味值為 yi。每頭奶牛都想要在她回牛棚的路上在某一個乾草捆處停留，但是她這樣做僅當經過這個乾草捆使她回牛棚的時間增加不超過這個乾草捆的美味值。注意一頭奶牛僅僅 “正式地” 在一個乾草捆處因進食而停留，即使她的路徑上經過其他放有乾草捆的牧場；她會簡單地無視其他的乾草捆。

輸入輸出格式#

輸入格式：
輸入的第一行包含三個空格分隔的整數 N，M 和 K。以下 M 行每行包含三個整數 ai，bi 和 ti，表示牧場 ai 和 bi 之間有一條需要 ti 時間通過的小路（ai 不等於 bi，ti 為不超過 10^4 的正整數）。
以下 K 行，每行以兩個整數描述了一個乾草捆：該乾草捆所在牧場的編號，以及它的美味值（一個不超過 10^9 的正整數）。同一片牧場中可能會有多個乾草捆。

輸出格式：
輸出包含 N-1 行。如果牧場 i 裡的奶牛可以在回牛棚的路上前往某一個乾草捆並且在此進食，則第 i 行為一個整數 1，否則為一個整數 0。

輸入輸出樣例#

輸入樣例 #1：

輸出樣例 #1：

1
1
1

說明#

在這個例子中，牧場 3 裡的奶牛可以停留進食，因為她回去的時間僅會增加 6（從 2 增加到 8），而這個增加量並沒有超過乾草捆的美味值 7。牧場 2 裡的奶牛顯然可以吃掉牧場 2 裡的乾草，因為這並不會導致她的最佳路徑發生變化。對於牧場 1 裡的奶牛是一個有趣的情況，因為看起來她的最佳路徑（10）可能會因為前去進食而有過大的增加量。然而，確實存在一條路徑使得她可以前去乾草捆處停留：先到牧場 4，然後去牧場 2（吃草），然後回到牧場 4。

思路#

大佬告訴我們，先再原圖上跑一遍 SPFA，得出每個點到 $n$ 的距離，存進 $d2$。
把美味度存進陣列 $a$
再從 $n + 1$ 連出一條指向有草的點的單向邊，邊權為 $d2 [i] - a [i]$
然後以 $n + 1$ 為源點再跑一遍 SPFA，存進 d1。
最後判斷 $d1 [i]$ 是否小於等於 $d2 [i]$。
原理呢。。。
一頭牛走到一個乾草堆，之後肯定要走它到 n 的最短路，那麼直接把 $d2 [i] - a [i]$ 連到 $n + 1$ 上，跑最短路，就能比較 $d [i]$ 與繞路走的路程之差是否小於 a [i]

代碼#

#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;
}