srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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;
}