【USACO18DEC】高級料理

[USACO18DEC] 高級料理#

グーグーグー。。。

何？前回の試験？

。。。暇があれば補習（安心して、あなたは暇じゃない）

問題#

長い一日が終わり、空腹に苦しむ牛たちが牛舎に戻る準備をしています。農場は N 枚の牧場で構成されており（2≤N≤50,000）、便宜上 1…N と番号が付けられています。すべての牛は牧場 N にある牛舎に向かう必要があります。他の N-1 枚の牧場にはそれぞれ 1 頭の牛がいます。牛たちは M 本の無向の小道を通って牧場間を移動できます（1≤M≤100,000）。第 i 本の小道は牧場 ai と bi を結び、通過するのに ti の時間がかかります。各牛は小道を通って牛舎に戻ることができます。

空腹のため、牛たちは帰る途中で食べ物を探すために少しの間立ち寄ることを喜んでいます。農場には K（1<=K<=N）個の美味しい干し草の束があり、第 i 個の干し草の束の美味しさは yi です。各牛は牛舎に戻る途中でどこかの干し草の束に立ち寄りたいと思っていますが、彼女がその干し草の束を通過することで牛舎に戻る時間がその干し草の束の美味しさを超えない場合に限ります。注意すべきは、牛は他の干し草の束が置かれている牧場を通過しても、あくまで「正式に」干し草の束の前で食事のために立ち寄るということです；彼女は他の干し草の束を無視します。

入力出力形式#

入力形式：
入力の最初の行には 3 つの空白で区切られた整数 N、M、K が含まれています。次の M 行にはそれぞれ 3 つの整数 ai、bi、ti が含まれ、牧場 ai と bi の間に通過するのに ti の時間がかかる小道があることを示します（ai は bi と異なり、ti は 10^4 を超えない正の整数です）。
次の K 行には、それぞれ 2 つの整数で干し草の束を説明します：その干し草の束がある牧場の番号と、その美味しさ（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;
}