QBBUILD - Xây dựng đường
Tác giả: RR
Ngôn ngữ: C++
#include <iomanip>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;
const double PI = acos(-1.0);
#define TWO(x) (1<<(x))
#define CONTAIN(S,x) (S & TWO(x))
int n, m, k;
int f[111][222], mark[111];
vector< pair<int,int> > ke[111];
set< pair<int, pair<int,int> > > s;
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d", &n); k = 4;
FOR(i,1,n) REP(mask,TWO(k)) f[i][mask] = 1000111000;
FOR(i,1,k) {
int u; scanf("%d", &u);
mark[u] = i;
f[u][TWO(i-1)] = 0;
s.insert(MP(0,MP(u,TWO(i-1))));
}
int u, v, c;
while (scanf("%d%d%d", &u, &v, &c) == 3) {
ke[u].PB(MP(v,c));
ke[v].PB(MP(u,c));
}
while (!s.empty()) {
int l = s.begin()->F;
pair<int,int> now = s.begin()->S;
int u = now.F, mask = now.S;
if (now.S == TWO(k) - 1) {
printf("%d\n", l);
return 0;
}
s.erase(s.begin());
// cout << u << ' ' << mask << endl;
REP(i,ke[u].size()) {
int v = ke[u][i].F, c = ke[u][i].S;
int mask2 = now.S;
if (mark[v]) mask2 |= TWO(mark[v] - 1);
int cost = f[u][mask] + c;
if (f[v][mask2] > cost) {
f[v][mask2] = cost;
s.insert(MP(f[v][mask2], MP(v, mask2)));
}
REP(mask3,TWO(k)) if ((mask3 & mask) == 0) {
int cost = f[u][mask] + f[v][mask3] + c;
if (f[v][mask3 | mask] > cost) {
f[v][mask3 | mask] = cost;
s.insert(MP(cost, MP(v, mask3 | mask)));
}
}
}
}
return 0;
}