Pagini recente » Cod sursa (job #2013881) | Cod sursa (job #1650348) | Cod sursa (job #1277451) | Cod sursa (job #1581766) | Cod sursa (job #1864949)
#include <iostream>
#include <limits.h>
#include <fstream>
#define DH 100005
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,c[100][100],t[100],d[100],viz[100],u[100];
void dijkstra(int x0)
{
int i,j,minn,ok,k;
for(i=1;i<=n;i++)
{
d[i]=c[x0][i];
t[i]=x0;
viz[i]=0;
}
t[x0]=0;
viz[x0]=1;
ok=1;
while(ok)
{
minn=INT_MAX;
for(i=1;i<=n;i++)
if(!viz[i] && minn>d[i])
{
minn=d[i];
k=i;
}
if(minn!=INT_MAX)
{
viz[k]=1;
for(i=1;i<=n;i++)
{
if(!viz[i] && d[i]>d[k]+c[k][i])
{
d[i]=d[k]+c[k][i];
t[i]=k;
}
}
}
else
ok=0;
}
}
void drum(int x)
{
if(t[x])
{
drum(t[x]);
g<<", "<<x;
}
else
g<<x;
}
int main()
{
int n,m,x,y,dist,i,x0=1,j,k;
f>>n>>m>>k;
for(i=1;i<=k;i++)
f>>u[k];
for(i=1;i<=m;i++)
{
f>>x>>y>>dist;
c[x][y]=dist;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(c[i][j]==0)
c[i][j]=DH;
dijkstra(1);
drum(n);
return 0;
}