Codeforces Round #374 (Div. 2) C. Journey

問題
n個の名所がある。
名所間を移動するのに必要な時間が与えられる。
1つ目の名所からスタートして、時間T以内にn個目の名所に辿りつかないといけない。
なるべく多くの名所を周りたい場合、どのような順番で名所を訪れればよいか出力せよ。

解法
本番はダイクストラをした。
他の人のソース見たら、みんなトポロジカル順序でDPしてて焦った。
絶対落ちたわーと絶望していたら通っていた。
が、この問題はトポロジカル順序DPで解いた方がかっこいい。

ソース

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

const int INF = 1<<30;
int n, m, t;
int dp[5050][5050];  // dp[i][j]: at j-th place and visited i+1 place
int pre[5500][5050];
vector<pair<int, int> > edges[5050];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m >> t;
  REP (i, m) {
    int v,u,w;
    cin >> v >> u >> w;
    edges[--v].emplace_back(--u, w);
  }

  REP (i, 5050) REP (j, 5050) { dp[i][j] = INF; pre[i][j] = -1; }
  dp[0][0] = 0;

  REP (i, n) REP (j, n) {
    if (dp[i][j] == INF) continue;
    for (auto &e : edges[j]) {
      int k, w;
      tie(k, w) = e;
      if (dp[i][j] + w < dp[i+1][k]) {
        dp[i+1][k] = dp[i][j] + w;
        pre[i+1][k] = j;
      }
    }
  }

  int v = n-1;
  int c = -1;
  REP (i, n) if (dp[i][v] <= t) c = i;

  vector<int> r;
  while (v) {
    r.push_back(v+1);
    v = pre[c--][v];
  }
  r.push_back(1);
  reverse(ALL(r));

  cout << r.size() << endl;
  for (auto &x: r)
    cout << x << " ";
  cout << endl;

  return 0;
}