Pagini recente » Cod sursa (job #515984) | Cod sursa (job #1759126) | Cod sursa (job #2887894) | Cod sursa (job #1047450) | Cod sursa (job #883410)
Cod sursa(job #883410)
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#define MAXN 1024
using namespace std;
int matPaths[MAXN][MAXN];
short used[MAXN];
short dist[MAXN];
bitset<MAXN> bitsetVisited;
struct Edge
{
Edge() :
DestNode(0),
Cost(0)
{}
Edge(short destNode, short cost) :
DestNode(destNode),
Cost(cost)
{}
short DestNode;
short Cost;
};
static ostream& operator << (ostream& os, const Edge& e)
{
os << "(" << e.DestNode << " " << e.Cost << ")";
return os;
}
struct Entry
{
Entry() :
Cost(0),
NodeList(0)
{}
Entry(short nodeList, int cost) :
Cost(cost),
NodeList(nodeList)
{}
int Cost;
short NodeList;
bool operator < (const Entry& rhs) const
{
return Cost > rhs.Cost;
}
};
int n, m, k;
vector<Edge> graphForwardEdges[MAXN];
void DFS(const short node)
{
if (node == n) return;
for (vector<Edge>::const_iterator it=graphForwardEdges[node].begin(); it!=graphForwardEdges[node].end(); ++it)
{
if (bitsetVisited[it->DestNode] == false)
{
bitsetVisited[it->DestNode] = true;
DFS(it->DestNode);
}
}
::fill(used, used+n+1, 0);
priority_queue<Entry> pqPathCosts;
for (vector<Edge>::const_iterator it=graphForwardEdges[node].begin(); it!=graphForwardEdges[node].end(); ++it)
{
if (matPaths[it->DestNode][0] > 0)
{
used[it->DestNode] = 1;
dist[it->DestNode] = it->Cost;
pqPathCosts.push(Entry(it->DestNode, matPaths[it->DestNode][1] + it->Cost));
}
}
// perform n-way merge sort
while (pqPathCosts.empty() == false && matPaths[node][0] < k)
{
const Entry entry = pqPathCosts.top();
pqPathCosts.pop();
matPaths[node][++matPaths[node][0]] = entry.Cost;
if (used[entry.NodeList] < matPaths[entry.NodeList][0])
{
++used[entry.NodeList];
pqPathCosts.push(Entry(entry.NodeList, matPaths[entry.NodeList][used[entry.NodeList]] + dist[entry.NodeList]));
}
}
}
int main()
{
fstream fin("pitici.in", fstream::in);
fstream fout("pitici.out", fstream::out);
fin >> n >> m >> k;
//cout << n << " " << m << " " << k << endl;
for (int i=0; i<m; ++i)
{
short x, y, c;
fin >> x >> y >> c;
graphForwardEdges[x].push_back(Edge(y, c));
}
matPaths[n][0] = 1;
bitsetVisited[1] = true;
DFS(1);
ostream_iterator<int> itOut(fout, " ");
copy(&matPaths[1][1], &matPaths[1][1] + k, itOut);
fout << "\n";
return 0;
}