Submission #4033318

---

Source Code Expand

#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

static const ll MAX = 201; // number of vertex
static const ll INF = mop;
static const ll whi = 0;
static const ll gra = 1;
static const ll bla = 2;

ll n, adj[MAX][MAX]; // adjacency matrix
ll d[MAX][MAX];

void dijkstra(ll k){
    ll minv;
    ll color[MAX];

    for (ll i=1;i<=n;i++){
        d[k][i] = INF;
        color[i] = whi;
    }

    d[k][k] = 0; // starting point distance
    color[k] = gra;
    while(true){
        minv = INF;
        ll u = -1;
        for (ll i=1;i<=n;i++){
            if(minv > d[k][i] and color[i] != bla){
                u = i;
                minv = d[k][i];
            }
        }
        if(u == -1){
            break;
        }
        color[u] = bla;
        for (ll v=1;v<=n;v++){
            if(color[v] != bla and adj[u][v] != INF){
                if(d[k][v] > d[k][u] + adj[u][v]){
                    d[k][v] = d[k][u] + adj[u][v];
                    color[v] = gra;
                }
            }
        }
    }
}


int main() {
   
    ll m,r;
    cin >> n >> m >> r;
    vector <ll> des;
    for (ll i=0;i<r;i++){
        ll x;
        cin >> x;
        des.push_back(x);
    }
    for (ll i=1;i<=n;i++){
        for (ll j=1;j<=n;j++){
            adj[i][j] = INF;
        }
    }
    for(ll i=0;i<m;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }
//    for (ll i=1;i<=n;i++){
//        if(i-1){
//            cout << endl;
//        }
//        for(ll j=1;j<=n;j++){
//            cout << adj[i][j] << " ";
//        }
//    }
//    cout << endl;
    for (ll i=1;i<=n;i++){
        dijkstra(i);
    }

    ll ans = INF;
  	sort(des.begin(), des.end());
    do{
        ll pre = 0;
        for (ll i=0;i<r-1;i++){
            pre += d[des[i]][des[i+1]];
        }
        if(ans > pre){
            ans = pre;
        }
    }while(next_permutation(des.begin(), des.end()));

    cout << ans << endl;
//    for (ll i=1;i<=n;i++){
//        for (ll j=1;j<=n;j++){
//            cout << i << " " << j << " " << d[i][j] << endl;
//        }
//    }



}

Submission Info

Judge Result