Pagini recente » Cod sursa (job #2988315) | Cod sursa (job #1875309) | Cod sursa (job #2317209) | Cod sursa (job #912592) | Cod sursa (job #3143251)
#include <bits/stdc++.h>
using namespace std;
const int V_MAX = 2000;
const int E_MAX = 10e3;
const int K_MAX = 2 + 15;
const int MASK_MAX = (1 << K_MAX);
ifstream in ("ubuntzei.in");
ofstream out ("ubuntzei.out");
struct defEdge {
int to, cost;
}; vector<defEdge> g[V_MAX];
defEdge makeEdge (int to, int cost) {return {to, cost};};
int target[K_MAX];
int V, E, K;
void initRead (void) {
in >> V >> E;
in >> K;
target[0] = 0;
for (int i = 1; i <= K; i ++)
in >> target[i], target[i] --;
target[K + 1] = V - 1; K += 2;
for (int i = 0; i < E; i ++) {
int u, v, cost; in >> u >> v >> cost; u --, v --;
g[u].push_back (makeEdge (v, cost));
g[v].push_back (makeEdge (u, cost));
}
}
const int myINF = 2e9;
struct defDist {
int dist, node;
}; bool operator < (defDist P, defDist Q) {return P.dist > Q.dist;}
defDist makeDist (int dist, int node) {return {dist, node};}
int minDist[K_MAX][1 + V_MAX];
void initDist (void) {
for (int i = 0; i < K; i ++)
for (int node = 0; node < V; node ++)
minDist[i][node] = myINF;
}
void Dijkstra (int index) {
int source = target[index];
minDist[index][source] = 0;
priority_queue<defDist> pq; pq.push (makeDist (0, source));
while (!pq.empty ()) {
defDist best = pq.top (); pq.pop ();
int node = best.node, dist = best.dist;
for (defEdge e : g[node]) {
int to = e.to, cost = e.cost;
if (dist + cost < minDist[index][to])
minDist[index][to] = dist + cost, pq.push (makeDist (minDist[index][to], to));
}
}
}
int dp[K_MAX][MASK_MAX];
void initDP (void) {
for (int i = 0; i < K; i ++)
for (int mask = 0; mask < (1 << K); mask ++)
dp[i][mask] = myINF;
dp[0][1] = 0;
}
int main()
{
initRead ();
initDist ();
for (int t = 0; t < K; t ++)
Dijkstra (t);
initDP ();
for (int mask = 0; mask < (1 << K); mask ++)
for (int i = 0; i < K; i ++)
for (int j = 0; j < K; j ++)
if (mask & (1 << i) && i != j)
dp[j][mask | (1 << j)] = min (dp[j][mask | (1 << j)], dp[i][mask] + minDist[i][target[j]]);
out << dp[K - 1][(1 << K) - 1];
return 0;
}