loj 10078 / 一本通 1500 / 洛谷 P5764【最短路】【dfs枚举排列】

没想到这么暴力的做法竟然卡过去了……

我想 dfs 应该可以优化，欢迎评论区留言。

#include 

using namespace std;

const int N = 2e5 + 10;
vector <pair <int, int> > z[N];
int dis[6][N];
int s[6];
bool vis[N], vis2[N];

void dij(int st, int d[])
{
  memset (d, 0x3f, N * sizeof(int));
  d[st] = 0;
  memset (vis, false, sizeof vis);
  priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
  pq.push(make_pair(0, st));
  while (pq.size())
  {
    auto t = pq.top();
    pq.pop();
    if (vis[t.second])
      continue ;
    vis[t.second] = true;
    for (auto &u : z[t.second])
      if (d[u.first] > d[t.second] + u.second)
      {
        d[u.first] = d[t.second] + u.second;
        pq.push(make_pair(d[u.first], u.first));
      }
  }
}

int dfs(int u, int st = 0, int d = 0)
{
  if (u > 5)
    return d;
  int res = 1e9;
  for (int i = 1; i <= 5; i ++)
    if (!vis2[i])
    {
      int g = s[i];
      vis2[i] = true;
      res = min(res, dfs(u + 1, i, d + dis[st][g]));
      vis2[i] = false;
    }
  return res;
}

signed main()
{
  int n, m;
  cin >> n >> m;
  s[0] = 1;
  for (int i = 1; i <= 5; i ++)
    cin >> s[i];
  while (m --)
  {
    int a, b, c;
    cin >> a >> b >> c;
    z[a].push_back(make_pair(b, c));
    z[b].push_back(make_pair(a, c));
  }
  for (int i = 0; i < 6; i ++)
    dij(s[i], dis[i]);
  cout << dfs(1) << '\n';
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69