QBBUILD - Xây dựng đường
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int n;
int id[4];
int a[101][101];
int inf;
int main() {
scanf("%d", &n);
for(int i=0;i<4;++i) scanf("%d", &id[i]);
inf = 1000000000;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j) a[i][j] = inf;
else a[i][j] = 0;
{
int u, v, c;
while(scanf("%d%d%d", &u, &v, &c)!=EOF) {
a[u][v] <?= c;
a[v][u] <?= c;
}
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j] <?= a[i][k] + a[k][j];
int result = inf;
sort( id, id+4);
do {
for(int u=1;u<=n;++u)
for(int v=1;v<=n;++v)
result <?= a[u][id[0]] + a[u][id[1]] + a[v][id[2]] + a[v][id[3]] + a[u][v];
} while(next_permutation(id,id+4));
printf("%d\n", result);
return 0;
}