Cod sursa(job #2719585)

Utilizator stefan1anubystefan popa stefan1anuby Data 9 martie 2021 23:42:09
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 2005
#define KMAX 18
#define INF 2e9

vector < pair < int, int > > G[NMAX];
priority_queue < pair < int, int > > Q;
int C[NMAX],Cost[KMAX][KMAX],DP[NMAX][KMAX];
int N,M,K;

void read()
{
    int i,j,x,y,z;
    cin>>N>>M;
    cin>>K;
    for(i=1; i<=K; i++)
        cin>>C[i];
    for(i=1; i<=M; i++)
    {
        cin>>x>>y>>z;
        G[x].push_back({y,z});
        G[y].push_back({x,z});
    }
}

int d[NMAX+2];
void Dijkstra(int start)
{
    int i;
    for(i=1; i<=N; i++)
        d[i]=INF;
    Q.push({0,start});/// vezi ca trebuie sa fie cu - ca sa aflu cel mai mic numar din coada
    d[start]=0;
    while(Q.empty()==false)
    {
        int node=Q.top().second;
        Q.pop();
        for(auto edge: G[node])
        {
            int next_node=edge.first;
            int next_cost=edge.second;
            if(d[node]+next_cost<d[next_node])
            {
                d[next_node]=d[node]+next_cost;
                Q.push({-d[next_node],next_node});
            }
        }
    }
}

void getCost()
{
    int i,j;
    for(i=1; i<=K; i++)
        for(j=1; j<=K; j++)
            Cost[i][j]=INF;
    Dijkstra(1);
    for(i=1; i<=K; i++)
    {
        Dijkstra(C[i]);
        for(j=1; j<=K; j++)
            Cost[i][j]=d[C[j]];
    }
    Dijkstra(N);
}

void afis()
{
    int i,j;
    for(i=1; i<=K; i++)
    {
        for(j=1; j<=K; j++)
            cout<<Cost[i][j]<<" ";
        cout<<endl;
    }
}

/// DP[i][j] : drumul optim care se termina in j avand bitii din i activati
void solve()
{
    int i,j;
    /*read();
    getCost();*/
    for(i=1;i < 1<<10;)
    {
        i<<=1;
        cout<<i<<" ";
    }
}

int main()
{
    solve();
//  afis();
    return 0;
}