ABC137のE - Coins Respawn

感想

AtCoder Beginner Contest 137のCoins Respawn。

自分のようなビギナーには、グラフ問題のエッセンスが詰まったような問題でいろいろ勉強になった。

ポイント

1. Pは辺のコストとしてまとめて考えることができる
2. 辺のコストに-1かけることで、最短経路問題にできる
3. 負の閉路がある可能性があるのでベルマンフォード法を使う
4. 逆辺でつくったグラフをBFSやらDFSで探索することでゴールにたどり着ける頂点を事前に調べる

コード

typedef long long ll;

struct edge {int from;int to;ll cost;};
vector<edge> es;

ll dist[2505];
ll inf=1ll<<50;
vector<int> rev_g[2505];
int ok[2505];
ll n,m,p;

void bfs(int v) {
  ok[v]=1;
  for(auto u : rev_g[v]) {
    if(ok[u])continue;
    bfs(u);
  }
}

void solve_bf(){
  dist[0]=0;
  for(int i=0;i<n;i++){
    bool update = 0;
    for(auto e : es) {
      if(ok[e.to] && dist[e.from] != inf && dist[e.to]>dist[e.from]+e.cost){
        dist[e.to]=dist[e.from]+e.cost;
        update=1;
      }
    }
    if(!update)break;
    if(i==n-1){
      cout<<-1<<endl;
      exit(0);
    }
  }
}

int main(int argc, char *argv[]) {
  for(int i=0;i<2505;i++)dist[i]=inf;

  cin>>n>>m>>p;
  for(int i=0;i<m;i++){
    int a,b;ll c;cin>>a>>b>>c;a--;b--;
    es.push_back({a,b,-c+p});
    rev_g[b].push_back(a);
  }

  bfs(n-1);
  solve_bf();

  cout<<max(dist[n-1]*-1, 0ll)<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?