Problem

You have just moved into a new apartment and have a long list of items you need to buy. Unfortunately, to buy this many items requires going to many different stores. You would like to minimize the amount of driving necessary to buy all the items you need.

Your city is organized as a set of intersections connected by roads. Your house and every store is located at some intersection. Your task is to find the shortest route that begins at your house, visits all the stores that you need to shop at, and returns to your house.

Code(dijkstra)

```#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
int to, cost;
Edge(int to, int cost):to(to), cost(cost) {}
};
const int maxn = 102400, inf = 0x3f3f3f3f;
int N, M, D[20][maxn], V[20], pos[maxn];
vector<Edge> G[maxn];

void dijkstra(int s, int d[]) {
d[s] = 0;
priority_queue<P, vector<P>, greater<P>> qu;
qu.push(P(0, s));
while (!qu.empty()) {
P p = qu.top(); qu.pop();
int u = p.second;
if (d[u] < p.first) continue;
for (Edge &e : G[u]) {
if (d[e.to] > p.first + e.cost) {
d[e.to] = p.first + e.cost;
qu.push(P(d[e.to], e.to));
}
}
}
}

int main()
{
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &N, &M);
for(int i = 0; i < maxn; ++i)
G[i].clear();
memset(D, inf, sizeof(D));
for(int i = 0; i < M; ++i) {
int x, y, w; scanf("%d%d%d", &x, &y, &w);
G[x].push_back(Edge(y, w));
G[y].push_back(Edge(x, w));
}
int S; scanf("%d", &S);
for(int i = 1; i <= S; ++i)
scanf("%d", V + i);
sort(V + 1, V + S + 1);
dijkstra(0, D[0]);
for(int i = 1; i <= S; ++i) {
dijkstra(V[i], D[i]);
pos[V[i]] = i;
}
int best = inf;
do {
int cur = D[0][V[1]] + D[0][V[S]];
for(int i = 1; i < S; ++i)
cur += D[pos[V[i]]][V[i+1]];
best = min(best, cur);
} while(next_permutation(V + 1, V + S + 1));
printf("%d\n", best);
}
return 0;
}
```

Code(SPFA)

```#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
int to, cost;
Edge(int to, int cost):to(to), cost(cost) {}
};
const int maxn = 102400, inf = 0x3f3f3f3f;
int N, M, D[20][maxn], V[20], pos[maxn];
int inq[maxn], cnt[maxn];
vector<Edge> G[maxn];

bool spfa(int st, int d[]) {
queue<int> qu;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
d[st] = 0; inq[st] = true; qu.push(st);
while(!qu.empty()) {
int u = qu.front(); qu.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if(d[u] < inf && d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
if(!inq[e.to]) {
qu.push(e.to);
inq[e.to] = true;
if(++cnt[e.to] > N)
return false;
}
}
}
}
return true;
}

int main()
{
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &N, &M);
for(int i = 0; i < maxn; ++i)
G[i].clear();
memset(D, inf, sizeof(D));
for(int i = 0; i < M; ++i) {
int x, y, w; scanf("%d%d%d", &x, &y, &w);
G[x].push_back(Edge(y, w));
G[y].push_back(Edge(x, w));
}
int S; scanf("%d", &S);
for(int i = 1; i <= S; ++i)
scanf("%d", V + i);
sort(V + 1, V + S + 1);
spfa(0, D[0]);
for(int i = 1; i <= S; ++i) {
spfa(V[i], D[i]);
pos[V[i]] = i;
}
int best = inf;
do {
int cur = D[0][V[1]] + D[0][V[S]];
for(int i = 1; i < S; ++i)
cur += D[pos[V[i]]][V[i+1]];
best = min(best, cur);
} while(next_permutation(V + 1, V + S + 1));
printf("%d\n", best);
}
return 0;
}
```