codeforces 374 div2 C. Journey
問題概要
有向グラフが与えられる。1からnまで距離T以下で行く中で、辿る頂点の数を最大にする経路を求める。
解法
dpの解法は、dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 として更新していけば解くことができた。今回の問題は有向グラフでループがないので、dpで解ける。自分がよくわからないかったのは、どういう順番でループの処理を書けばよいかであった。いくつの名所を回ったかを外側のループに持ってきて、内側に現在の場所のループを持ってこればかけるみたい。この辺が難しい。再帰関数で書けばすんなりいく?
ダイクストラでも解ける。priorityqueueには、距離、現在の頂点、いくつの頂点を回ってきたかを入れる。また、普通のダイクストラの場合はdist[i]で頂点iまでの距離をいれて、更新するだけでよいが、今回は、もう一つ状態として、いくつの頂点を回ってきたかを持っているので、dist[u][num] := 現在の頂点がuで廻った頂点の数が、numの時の最短距離 としてやればいける。これが頂点に属性を加えて(今回の場合は何個の名所を辿ってきたか)、同じ頂点を別々の頂点としてあつかう拡張ダイクストラ??
でもやってることは、ただのダイクストラと違いはないよね、ただ、値を更新していく際に、状態が増えているだけか。
ミス
本番はダイクストラで書いたけど落とされた。勉強になった。
コード
dp
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int n, m, T; vector<pair<int, int> > G[5010];//fi 頂点番号 se 距離 //dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 int dp[5010][5010]; //back[cnt][v] := vでcnt個の名所を回ったとき、vの前の町は、u u -> v int back[5010][5010]; const int INF = 1e9 + 10; int main(void){ cin >> n >> m >> T; rep(i, m){ int u, v, cost; cin >> u >> v >> cost; u--; v--; G[u].push_back(make_pair(v, cost)); } rep(i, 5010)rep(j, 5010) dp[i][j] = INF; dp[0][0] = 0; ll len; for (int cnt = 0; cnt < n - 1; ++cnt){ for (int u = 0; u < n; ++u){ if(dp[cnt][u] == INF) continue; for(auto v : G[u]){ //u -> vへ len = dp[cnt][u] + v.second; //同じ数の名所を回って、v.firstにいるときの最短距離更新 if(len < dp[cnt + 1][v.first]){ dp[cnt + 1][v.first] = len; back[cnt + 1][v.first] = u; } } } } //距離T以下で行ける最大の名所の数を求める int num; for (int cnt = n - 1; cnt >= 0; --cnt){ if(dp[cnt][n - 1] <= T){ num = cnt; break; } } //経路復元 vector<int> ans; ans.push_back(n - 1); queue<pair<int, int> > que; que.push(make_pair(num, n - 1)); while(1){ int cnt = que.front().first, v = que.front().second; que.pop(); if(v == 0) break; int u = back[cnt][v]; ans.push_back(u); que.push(make_pair(cnt - 1, u)); } reverse(ans.begin(), ans.end()); printf("%d\n", ans.size()); rep(i, ans.size()){ printf("%d ", ans[i] + 1); } return 0; }
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <tuple> using namespace std; typedef long long ll; typedef tuple<int, int, int> tup; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9 + 10; int n, m, T; vector<pair<int, int> > G[5010]; //dist[u][num] := 現在の頂点がuで廻った頂点の数が、numの時の最短距離 int dist[5010][5010]; //back[v][cnt] := vでcnt個の名所を回ったとき、vの前の町は、u u -> v int back[5010][5010]; void dijkstra(void){ rep(i, 5010)rep(j, 5010) dist[i][j] = INF; priority_queue<tup, vector<tup>, greater<tup> > q; q.push(make_tuple(0, 0, 0));//距離 現在の頂点 いくつの頂点を廻ったか while(!q.empty()){ int cost, u, num; tie(cost, u, num) = q.top(); q.pop(); if(dist[u][num] < cost) continue; for (auto tmp : G[u]){ int v = tmp.first, len = tmp.second; if(cost + len < dist[v][num + 1]){//最短距離更新 dist[v][num + 1] = cost + len; q.push(make_tuple(dist[v][num + 1], v, num + 1)); back[v][num + 1] = u; } } } } int main(void){ cin >> n >> m >> T; rep(i, m){ int u, v, cost; cin >> u >> v >> cost; u--; v--; G[u].push_back(make_pair(v, cost)); } dijkstra(); //距離T以下で行ける最大の名所の数を求める int num; for (int cnt = n - 1; cnt >= 0; --cnt){ if(dist[n - 1][cnt] <= T){ num = cnt; break; } } //経路復元 vector<int> ans; ans.push_back(n - 1); queue<pair<int, int> > que; que.push(make_pair(num, n - 1)); while(1){ int cnt = que.front().first, v = que.front().second; que.pop(); if(v == 0) break; int u = back[v][cnt]; ans.push_back(u); que.push(make_pair(cnt - 1, u)); } reverse(ans.begin(), ans.end()); printf("%d\n", ans.size()); rep(i, ans.size()){ printf("%d ", ans[i] + 1); } return 0; }