Pagini recente » Cod sursa (job #30068) | Cod sursa (job #815418) | Cod sursa (job #2109301) | Cod sursa (job #2544503) | Cod sursa (job #313936)
Cod sursa(job #313936)
#include <fstream>
#define DIM 50005
using namespace std;
struct nod {int x,c;
nod *urm;} *lst[DIM];
int cost[DIM],q[4*DIM+3];
int n,m;
void add (int a,int b,int c)
{
nod *p=new nod;
p->x=b;
p->c=c;
p->urm=lst[a];
lst[a]=p;
}
void read ()
{
ifstream fin ("dijkstra.in");
int i,x,y,ct;
fin>>n>>m;
for (i=1; i<=m; ++i)
{
fin>>x>>y>>ct;
add (x,y,ct);
}
}
void solve ()
{
ofstream fout ("dijkstra.out");
nod *p;
int i,in,sf;
for (q[in=sf=1]=1; in<=sf; ++in)
for (p=lst[q[in]]; p; p=p->urm)
if (!cost[p->x] || cost[q[in]]+p->c<cost[p->x])
{
cost[p->x]=cost[q[in]]+p->c;
q[++sf]=p->x;
}
for (i=2; i<=n; ++i)
fout<<cost[i]<<" ";
}
int main ()
{
read ();
solve ();
return 0;
}