ABC137 E. Coins Respawn - phyllo’s algorithm note

問題

1からNまで番号がついたN頂点M辺の有向グラフが与えられる。
頂点1から頂点Nまで辺を辿っていくことを考える。
辺iは通過するのに1分かかり、通るたびにコインがCi枚もらえる。
頂点Nにたどり着いておいてあるボタンを押すと「それまで回収したコインの総数から経過時間*P枚を引いたコイン枚数」が得られる。
(コインが足りない場合は0枚になる)
得られるコインが最大になるように行動した場合、何枚得られるか？
最大値が存在しない場合は-1を返せ。

制約

2 <= N <= 2500
1 <= M <= 5000
1 <= Ai, Bi <= N
1 <= Ci <= 10^5
0 <= P <= 10^5
有向グラフは1からNまで到達可能

解法

最長経路は辺のコストの正負を逆転させることで最短経路と同じ要領で求められる。
ただし、ループがあると最大値が無限に大きくできてしまうため、それを検出できるベルマンフォードで適用を考える。

単純に適用しようとすると、サンプルにある通り、「頂点1からたどり着けない頂点」、「頂点Nにたどり着けない頂点」も含めて閉路を検出してしまう。
なので上記のたどり着けない頂点をチェックして、その頂点を除いたグラフで適用すれば良い。

反省

「たどり着けるか？」の頂点のチェックにdfsではなくbfsで書いてしまったが、

queue<int> que;
while(!que.empty()){
  int x = que.front(); que.pop();
  visit[x] = true;
  FOR(it, g[x]){
    if(visit[it->dest]) continue;
    que.push(it->dest);
  }
}

のように書いてしまうと、O(N^2)で、
1->2, 1->3, ..., 1->N, 2->3, 2->4, ..., 2->N, ..., N-1->N
のようなグラフでTLEになってしまう。