Atcoder Beginner Contest 137 E でのTLE,WAの原因は何でしょうか

Question

質問

AtcoderBeginnerContest137-Eにおいて、WAやTLEが生じる原因がわからない。
(動作チェック用の出力をコメントアウトしてあります。)

問題文

1 から N までの番号がつけられた N 頂点と M 辺からなる有向グラフがあります。
i 番目の辺は頂点 A_i から頂点 B_i へと向かい、この辺の上には C_i 枚のコインが置かれています。
また、頂点 N にはボタンが設置されています。

このグラフ上でゲームを行います。 あなたは頂点 1 でコインを 0 枚持ってゲームを開始し、辺をたどってコインを拾いながら頂点 N を目指します。
1本の辺を通るには 1 分の時間がかかり、辺を通るたびにその辺の上に置かれているすべてのコインを拾うことができます。
ゲームの世界ではよくあるように、ある辺を通ってその上のコインを拾っても、その辺を次に通る際には同じ枚数のコインが再び出現しており、それらを再び拾うことができます。

頂点 N に到着したとき、ボタンを押してゲームを終了することができます。(ボタンを押さずに移動を続けることもできます。)
ただし、ゲームを終了する際に、ゲーム開始からの経過時間を T 分として T×P 枚のコインの支払いが要求されます。
持っているコインの枚数が T×P 枚未満の場合は、代わりに持っているコインをすべて支払います。

この支払いの後に残ったコインの枚数があなたのスコアとなります。 獲得できるスコアの最大値が存在するか判定し、存在する場合はその最大値を求めてください。

方針

• かかった時間に応じて最後に支払う -> 負の所持コインを許容し、辺を通るたびに支払う。
• 1(スタート)からN(ゴール)にたどり着けなくなる辺は除去。
• ベルマンフォード法を使用して最大を調べる。また、無限にコインを獲得するルートを検出。

結果

ほとんどはAC(正解)。一部WA(不正解)とTLEが生じる。

ソースコード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 100000

int N, M, P;

typedef struct edge
{
    int from;
    int to;
    int cost;
} edge;

int main()
{
    cin >> N >> M >> P;
    int dist[N + 1];//頂点ごとのコストを格納
    vector<edge> e1;//不要部分除去前の辺リスト
    vector<edge> e2;//不要部分除去後の辺リスト
    //コストの初期化
    for (int i = 1; i <= N; i++)
    {
        if (i != 1)
            dist[i] = INF;
        else
            dist[i] = 0;
    }
    //辺の登録
    {
        edge ed;
        for (int i = 0; i < M; i++)
        {
            cin >> ed.from >> ed.to >> ed.cost;
            ed.cost = P - ed.cost;
            e1.push_back(ed);
        }
    }
    //Nにたどり着けなくなる頂点、辺の除去
    {
        int fromOne[N + 1];//1からiにたどり着ける場合fromOne[i]=1 other 0
        int toN[N + 1];//iからNにたどり着ける場合toN[i]=1 other 0
        for (int i = 1; i <= N; i++)
        {
            fromOne[i] = 0;
            toN[i] = 0;
        }
        queue<int> que;
        que.push(1);
        while (!que.empty())
        {
            fromOne[que.front()] = 1;
            for (auto &&i : e1)
            {
                //cout << que.front() << "から移動" << endl;
                if (i.from == que.front() && fromOne[i.to] == 0)
                {
                    //cout << i.from << "->" << i.to << "へ移動" << endl;
                    que.push(i.to);
                }
            }
            que.pop();
        }
        //cout << "-------" << endl;
        que.push(N);
        while (!que.empty())
        {
            toN[que.front()] = 1;
            for (auto &&i : e1)
            {
                //cout << que.front() << "から移動" << endl;
                if (i.to == que.front() && toN[i.from] == 0)
                {
                    //cout << i.to << "->" << i.from << "へ移動" << endl;
                    que.push(i.from);
                }
            }
            que.pop();
        }
        for (auto &&i : e1)
        {
            if (fromOne[i.from] * toN[i.to] == 1)
            {
                e2.push_back(i);
            }
        }
    }
    //コストの緩和
    for (int i = 0; i < N; i++)
    {
        for (auto &&j : e2)
        {
            dist[j.to] = min(dist[j.to], dist[j.from] + j.cost);
        }
    }
    //負経路の探索
    for (auto &&i : e2)
    {
        if (dist[i.to] > dist[i.from] + i.cost)
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << max(-1 * dist[N], 0) << endl;
    return 0;
}

Answer 1

試していませんが、気になるのは

#define INF 100000

と

        while (!que.empty())
        {
            fromOne[que.front()] = 1;
            for (auto &&i : e1)
            {
                //cout << que.front() << "から移動" << endl;
                if (i.from == que.front() && fromOne[i.to] == 0)
                {
                    //cout << i.from << "->" << i.to << "へ移動" << endl;
                    que.push(i.to);
                }
            }
            que.pop();
        }

です
INFについては、一つの辺のコストが±10^5程なので、INFはN * 10^5ほどは確保しておかないと正しい結果にならない可能性があります。おそらくWAはこれが原因です。

もう一つがスタートとゴールそれぞれについて到達可能か調べる部分ですが、単純計算で外側のwhileが N 回、内側のforが M 回ループするので、O(NM)かかります。さらにこの書き方だと同じ頂点が繰り返しQueueにプッシュされるので、さらに悪くなります。おそらくこれがTLEの原因でしょう。