Răspuns:
#include <fstream>
#include <queue>
#include <climits>
using namespace std;
ifstream fin( "firma.in" );
ofstream fout( "firma.out" );
bool viz[ 101 ];
int dist[ 101 ], mat[ 101 ][ 101 ], n = 0, m = 0;
struct nod
{
int cost = 0;
int x = 0;
bool operator<( const nod& rhs ) const
{
return cost > rhs.cost;
}
};
priority_queue <nod> q;
void showqueue()
{
while( !q.empty() )
{
fout << q.top().x << " " << q.top().cost << " ";
q.pop();
}
}
void dijkstra( int start )
{
for( int i = 1; i <= n; ++i )
{
viz[ i ] = false;
if( mat[ start ][ i ] != INT_MAX )
{
dist[ i ] = mat[ start ][ i ];
nod a;
a.cost = dist[ i ];
a.x = i;
q.push( a );
}
else
{
dist[ i ] = INT_MAX;
}
}
dist[ start ] = 0;
viz[ start ] = true;
while( !q.empty() )
{
nod a;
a = q.top();
q.pop();
viz[ a.x ] = true;
for( int i = 1; i <= n; ++i )
{
if( !viz[ i ] && mat[ a.x ][ i ] != INT_MAX && dist[ i ] >= dist[ a.x ] + mat[ a.x ][ i ] )
{
dist[ i ] = dist[ a.x ] + mat[ a.x ][ i ];
nod curent;
curent.x = i;
curent.cost = dist[ i ];
q.push( curent );
}
}
}
}
int main()
{
fin >> n >> m;
for( int i = 1; i <= n; ++i )
{
for( int j = 1; j <= n; ++j )
{
mat[ i ][ j ] = INT_MAX;
}
}
int x = 0, y = 0, cost = 0, minim = 100000, indice = 0;
for( int i = 1; i <= m; ++i )
{
fin >> x >> y >> cost;
mat[ x ][ y ] = cost;
mat[ y ][ x ] = cost;
}
for( int i = 1; i <= n; ++i )
{
int suma = 0;
dijkstra( i );
for( int j = 1; j <= n; ++j )
{
suma += dist[ j ];
}
if( suma < minim )
{
minim = suma;
indice = i;
}
}
fout << indice;
return 0;
}
Explicație:
