#include <stdio.h>
#include <iostream>
using namespace std;
void beolvas(char*);
int n,m,h;
/*
struct elek
{
int w;
int suly;
};
*/
struct csucs_struct
{
int* el;
};
csucs_struct* cs;
bool* biztos;
int* apa;
int* d;
int ossz;
int at;
int main()
{
beolvas("futar.be8");
apa=new int[n+1];
biztos=new bool[n+1];
d=new int[n+1];
for(int i=1; i<n+1; i++)
{
apa[i]=10000;
d[i]=10000;
biztos[i]=false;
}
ossz=0;
d[h]=0;
at=h;
/* for(int i=1; i<n+1; i++)
{
for(int j=1; j<n+1; j++)
{
cout << cs[i].el[j]<<"\n";
}
}*/
while(ossz<n)
{
////////////////////////
int minh=0;
int min=10000;
for(int i=1; i<n+1; i++)
{
if(((d[i]<min) && (!biztos[i])))
{
min=d[i];
minh=i;
}
}
//////////////////////
at=minh;
// printf("AT: %d\n", at);
biztos[at]=true;
ossz++;
for(int i=1; i<n+1; i++)
{
int alt=d[at]+cs[at].el[i];
// printf("%d %d (%d %d)\n", alt, d[i], d[at], cs[at].el[i]);
if(alt<d[i])
{
d[i]=alt;
}
}
// for(int i=1; i<n+1; i++)
// printf("%d: %d\n", i, d[i]);
}
int min=0;
for(int i=1; i<n+1; i++)
{
// cout << d[i] << "\n";
if(d[i]>min)
{
min=d[i];
}
}
cout << min;
}
void beolvas(char* file)
{
FILE* be = fopen(file, "r");
fscanf(be, "%d", &n);
fscanf(be, "%d", &m);
fscanf(be, "%d", &h);
cs = new csucs_struct[n+1];
for (int i=1; i<n+1; i++)
{
cs[i].el=new int[n+1];
for(int j=1; j<n+1; j++)
{
cs[i].el[j]=10000;
}
}
for(int i=1; i<m+1; i++)
{
int t1,t2,t3;
fscanf(be, "%d", &t1);
fscanf(be, "%d", &t2);
fscanf(be, "%d", &t3);
if(cs[t1].el[t2]>t3)
{
cs[t1].el[t2]=t3;
// cout << i << " " << t1 << " " << t2 << " " << t3 << "\n";
}
}
}
2004-2016 BDG algoritmus szakkör