Cod sursa(job #3230283)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 20 mai 2024 13:56:37
Problema Pitici Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NMAX = 2002;

vector<pair<int, int>> v[NMAX];
int dp[NMAX][NMAX];
int vf[NMAX];

int n, m, k;

ifstream fin("pitici.in");
ofstream fout("pitici.out");

void dfs(int nod) {
    if(v[nod].size() == 0 || vf[nod] == 1)
        return ;

    vf[nod] = 1;
    set<tuple<int, int, int>> s;
    for(auto [vecin, cost] : v[nod]) {
        dfs(vecin);
        s.insert({dp[vecin][1] + cost, vecin, 1});
    }
    
    for(int i = 1; i <= k; i++) {
        auto [drum, vecin, cnt] = *s.begin();
        s.erase(s.begin());
        
        dp[nod][i] = drum;
        int cost = drum - dp[vecin][cnt];
        s.insert({dp[vecin][cnt + 1] + cost, vecin, cnt + 1});
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    fin >> n >> m >> k;

    int x, y, c;
    for(int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    
    memset(dp, INF, sizeof(dp));
    
    dp[n][1] = 0;
    
    dfs(1);
    
    for(int i = 1; i <= k; i++)
        fout << dp[1][i] << ' ';

    return 0;
}