Cod sursa(job #161470)

Utilizator victorsbVictor Rusu victorsb Data 18 martie 2008 11:17:16
Problema Pitici Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
/*
ID: victorsb
TASK: cowjog
LANG: C++
*/

#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 1024
#define Kmax 105
#define INF 0x3f3f3f3f
#define pb push_back
#define sz(a) (int)((a).size())

int n, m, k;
int D[Nmax][Kmax];
vector<int> lv[Nmax];
int cost[Nmax][Nmax];
int ind[Nmax];

void citire()
{
	int i, a, b, c;

	scanf("%d %d %d\n", &n, &m, &k);
	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d %d\n", &a, &b, &c);
		lv[b].pb(a);
		cost[b][a] = c;
	}
}

void solve()
{
	int i, j, pas, best;

	memset(D[1], 0x3f, sizeof(D[1]));
	D[1][1] = 0;

	for (i = 2; i <= n; ++i)
	{
		for (j = 0; j < sz(lv[i]); ++j)
			ind[lv[i][j]] = 1;

		for (pas = 1; pas <= k; ++pas)
		{
			D[i][pas] = INF;

			best = -1;
			for (j = 0; j < sz(lv[i]); ++j)
				if (D[i][pas] > D[lv[i][j]][ind[lv[i][j]]] + cost[i][lv[i][j]])
				{
					D[i][pas] = D[lv[i][j]][ind[lv[i][j]]] + cost[i][lv[i][j]];
					best = lv[i][j];
				}

			if (best > 0)
				++ind[best];
		}
	}

	for (i = 1; i <= k; ++i)
		if (D[n][i] < INF)
			printf("%d ", D[n][i]);
		else
			printf("-1\n");
}

int main()
{
	//freopen("cowjog.in", "r", stdin);
	//freopen("cowjog.out", "w", stdout);
	freopen("pitici.in", "r", stdin);
	freopen("pitici.out", "w", stdout);

	citire();
	solve();

	return 0;
}