next_permutationとワーシャルフロイド法(ABC 073 D問題)

・ダイクストラ法：単一始点 O(E * logV)
・ワーシャルフロイド法：全点 O(V^3)

問題
以下ネタバレ注意

1. ll dist[201][201];
2. int N, M, R;
3. int r[9];
4.  
5.  
6. int main() {
7. cin >> N >> M >> R;
8. REP(i, N) {
9. REP(j, N) {
10. dist[i][j] = INF;
11. }
12. }
13. REP(i, R) {
14. int k;
15. cin >> k;
16. r[i] = k - 1;
17. }
18. REP(i, M) {
19. int a, b, c;
20. cin >> a >> b >> c;
21. dist[a-1][b-1] = c;
22. dist[b-1][a-1] = c;
23. }
24. REP(k, N) { //kが中継点
25. REP(i, N) {
26. REP(j, N) {
27. dist[i][j] = min(dist[i][j], (dist[i][k] + dist[k][j]));
28. }
29. }
30. }
31. vector<int> v(R);
32. REP(i, R) {
33. v[i] = r[i];
34. }
35. VSORT(v);
36. ll ans = INF;
37. do {
38. ll cnt = 0;
39. REP(i, R - 1) {
40. cnt += dist[v[i]][v[i+1]];
41. }
42. ans = min(ans, cnt);
43. } while (next_permutation(v.begin(), v.end())); // 次の順列を生成
44. cout << ans << endl;
45. return 0;
46. }