# Cod sursa(job #428507)

Utilizator Data 29 martie 2010 12:20:03 Pitici 100 cpp done Arhiva de probleme 1.94 kb
``````#include <fstream>
#include <vector>
#include <set>

#define NMAX 1024
#define KMAX 1024
#define INFI 2000000
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

struct nod {int next, cost; };

set<pair<int, int> > H;
vector<nod> Gr[NMAX];

pair<int,int> heap[NMAX];

int A[NMAX][NMAX];

int N, M, K, S[NMAX], found, Viz[NMAX], best[NMAX][KMAX], heapLen;

int sortCond(pair<int, int> a, pair<int, int> b)
{
if (a.first < b.first) return 0;
else return 1;
}

{
ifstream fin("pitici.in");

fin >>N >>M >>K;

int i, x;
nod a;

for (i = 1; i <= M; i++)
{
fin >>x >>a.next >>a.cost;
Gr[x].pb(a);
}

fin.close();
}

void DFS(int x)
{
for (int i = 0; i < Gr[x].size(); i++)
if (Viz[Gr[x][i].next] == 0)
{
Viz[Gr[x][i].next] = 1;
DFS(Gr[x][i].next);
}
S[++found] = x;
}

void Solve(void)
{
DFS(1);

int i, x, j, nx, cc, indnx;

for (j = 1; j <= N; j++)
for (i = 1; i <= K; i++)
best[j][i] = INFI;

best[N][1] = 0;

i = 1;
while (S[i] != N) i++;
i++;

for (; i <= found; i++)
{
x = S[i];
heapLen = 0;

for (j = 1; j <= N; j++)
Viz[j] = 1;

if (Gr[x].size() > 0)
{
for (j = 0; j < Gr[x].size(); j++)
{
heap[heapLen++] = mp( best[ Gr[x][j].next ][ Viz[ Gr[x][j].next  ]++ ] + Gr[x][j].cost , j);
}
make_heap(heap, heap + heapLen, sortCond);

while (Viz[x] <= K)
{
best[x][Viz[x]++] = heap[0].ff;
indnx = heap[0].ss;
nx = Gr[x][heap[0].ss].next;
cc = Gr[x][heap[0].ss].cost;
pop_heap(heap, heap + heapLen, sortCond);
heapLen--;

if (Viz[nx] <= K)
{
heap[heapLen++] = mp( best[ nx ][ Viz[nx]++ ] + cc , indnx );
push_heap(heap, heap + heapLen, sortCond);
}
}
}
}
}
void writeResult(void)
{
ofstream fout("pitici.out");

for(int i = 1; i <= K; i++)
fout <<best[1][i] <<' ';

fout.close();
}

int main()
{