ワーシャルフロイド(ABC073D - joisino's travel)

atcoder.jp
簡単な問題が続いている…
通る頂点が8個と少ないので、この8つの頂点からの各頂点への最短距離を求めておく。
まあ全頂点間でも間に合うしめんどくさいのでそうする。ワーシャルフロイド（計算量）
あとは8!通りの通り方についてこれを使って合計距離を求め、一番短いものを採用

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

struct Warshall_Floyd{
    int V;
    long long int *d;//d[i_v1*V+i_v2]= v1tov2
    vector<  pair<int,int>  > *edges;
    Warshall_Floyd(int N): V(N){
        d = new long long int[V*V];
        edges=new vector<  pair<int,int>  >[V];
        rep(i,V*V){
            d[i]=LLINF;
        }
    }
    void push_edges(int a,int b, int c){
        edges[a].pb( mp(c,b));
        edges[b].pb( mp(c,a));
        if(ite(a,b)>c)d[a*V+b]=c;
        if(ite(b,a)>c)d[b*V+a]=c;
    }
    long long int ite(int i,int j){
        return d[i*V+j];
    }
    void solve() { 
        for (int i = 0; i < V; i++)      // via
        for (int j = 0; j < V; j++)    // start
        for (int k = 0; k < V; k++)  // end
         d[j*V+k] = min(ite(j,k), ite(j,i) + ite(i,k));
    }
    void free_wf(){
        delete[] d;
        delete[] edges;
    }
    
};

int main(void){
    int N,M,R;
    scanf("%d %d %d",&N,&M,&R);
    Warshall_Floyd WF(N);
    vector<int> r;
    rep(i,R){
        int _r;
        scanf("%d",&_r);_r--;
        r.pb(_r);
    }
    rep(i,M){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a--;b--;
        WF.push_edges(a,b,c);
    }
    WF.solve();
    sort(r.begin(), r.end());
    long long int ans=LLINF;
    do{
        long long int sans=0;
        rep(i,r.size()-1){
            sans+=WF.ite(r[i],r[i+1]);
        }
        ans=min(ans,sans);
    }while (next_permutation(r.begin(), r.end()));
    printf("%lld\n",ans);
}