Pagini recente » Cod sursa (job #3221875) | Cod sursa (job #3209099) | Cod sursa (job #10686) | Cod sursa (job #38950) | Cod sursa (job #2126098)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("team.in");
ofstream fout("team.out");
typedef pair<int,int> str;
const int DIM = 505;
const int INF = 0x3f3f3f3f;
int P, N, M, Dist[55][DIM], C[DIM][DIM], Dp[55][55][55], Home[55];
vector<int> Edge[DIM];
priority_queue< str, vector<str>, greater<str> > q;
inline void dijkstra( int pos ){
memset( Dist[pos], INF, sizeof(Dist[pos]) );
Dist[pos][ Home[pos] ] = 0;
q.push( { 0, Home[pos] } );
while( !q.empty() ){
int nod = q.top().second;
int Lg = q.top().first;
q.pop();
if( Dist[pos][nod] != Lg )
continue;
for( int i = 0; i < Edge[nod].size(); i++ ){
int vecin = Edge[nod][i];
if( Dist[pos][vecin] > Dist[pos][nod] + C[nod][vecin] )
Dist[pos][vecin] = Dist[pos][nod] + C[nod][vecin], q.push( { Dist[pos][vecin], vecin } );
}
}
}
int solve( int i, int j, int k ){
if( i > j )
return 0;
if( Dp[i][j][k] != 2 * INF )
return Dp[i][j][k];
for( int cross = i; cross <= j; cross++ ){
//formez grupul i..j reunind grupurile i..cross-1 si cross+1...j cu persoana de legatura cross in orasul acesteia
Dp[i][j][k] = min( Dp[i][j][k], Dist[k][ Home[cross] ] +
solve( i, cross - 1, cross ) + solve( cross + 1, j, cross ) );
}
return Dp[i][j][k];
}
int main(){
fin >> P >> N >> M;
for( int i = 1; i <= M; i++ ){
int a, b; fin >> a >> b;
fin >> C[a][b]; C[b][a] = C[a][b];
Edge[a].push_back( b );
Edge[b].push_back( a );
}
Home[1] = 1;
for( int i = 2; i <= P + 1; i++ )
fin >> Home[i];
P++;
for( int i = 1; i <= P; i++ )
dijkstra( i );
//Dp[i][j][k] = costul minim pentru ca persoanele i...j sa ajunga acasa pornind din orasul persoanei k
for( int i = 0; i <= P; i++ )
for( int j = 0; j <= P; j++ )
for( int k = 0; k <= P; k++ )
Dp[i][j][k] = 2 * INF;
for( int i = 1; i <= P; i++ )
Dp[i][i][i] = 0;
fout << solve( 1, P, 1 ) << "\n";
return 0;
}