Cod sursa(job #2443594)

Utilizator CharacterMeCharacter Me CharacterMe Data 28 iulie 2019 17:42:54
Problema Pitici Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, k, i, j, in[1020], p, ind[1020];
vector<pair<int, int> > graph[1020], rev[1020];
vector<int> sol[1020];
queue<int> q;
char c[30];
int read();
void inter(int node);
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
int main()
{
    freopen("pitici.in", "r", stdin);
    freopen("pitici.out", "w", stdout);
    fgets(c, 30, stdin); p=-1;
    n=read(); m=read(); k=read();
    for(i=1; i<=m; ++i){
        int x, y, z;
        fgets(c, 30, stdin); p=-1;
        x=read(); y=read(); z=read();
        graph[x].push_back({y, z});
        rev[y].push_back({x, z});
        ++in[y];
    }
    sol[1].push_back(0);
    for(q.push(1); !q.empty(); q.pop()){
        int node=q.front();
        if(node!=1)inter(node);
        for(auto i:graph[node]){
            --in[i.first];
            if(in[i.first]==0) q.push(i.first);
        }
    }
    for(i=0; i<k; ++i) printf("%d ", sol[n][i]);
    return 0;
}
int read(){
    ++p; int nr=0;
    while(c[p]!='\n' && c[p]!=' ') {nr=nr*10+(c[p]-'0'); ++p;}
    return nr;
}
void inter(int node){
    while(!pq.empty()) pq.pop();
    for(int i=0; i<rev[node].size(); ++i) pq.push({sol[rev[node][i].first][0]+rev[node][i].second, i});
    for(int i=1; i<=k && !pq.empty(); ++i, pq.pop()){
        pair<int, int> init=pq.top();
        sol[node].push_back(init.first); int next=rev[node][init.second].first;
        if(ind[next]+1==sol[next].size()) continue;
        pq.push({sol[next][++ind[next]]+rev[node][init.second].second, init.second});
    }
    return;
}