Submission #74228567

---

Source Code Expand

#include <iostream>
#include <vector>
#include<map>
#include<set>
#include<deque>
#include <queue>
#include <functional>

using namespace std;
#define int long long
const int inf = 1e18;

void solve(){

    int n, m; cin >> n >> m;

    vector<vector<int>> dist(n + 1, vector<int>(n + 1, inf));

    for(int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;

        dist[u][v] = w;
    }

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){

                //i -> j => i k + k j;
                if(dist[i][k] != inf && dist[k][j] != inf){
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    for(int i = 1; i <= n; i++){
        dist[i][i] = 0;
    }

    int src, k; cin >> src >> k;

    vector<int> node(k);
    for(auto &i: node) cin >> i;

    int mx = 1LL << k;
    vector<vector<int>> dp(mx, vector<int>(k, inf));

    for(int u = 0; u < k; u++){
        
        if(dist[src][node[u]] == inf) continue;

        dp[1LL << u][u] = dist[src][node[u]];
    }

    for(int mask = 0; mask < mx; mask++){

        for(int u = 0; u < k; u++){
            if(dp[mask][u] == inf) continue;

            for(int v = 0; v < k; v++){
                
                if(dist[node[u]][node[v]] == inf) continue;
                int newMaks = mask | (1LL << v);

                dp[newMaks][v] = min(dp[newMaks][v], dp[mask][u] + dist[node[u]][node[v]]);
            }
        }
    }

    int res = inf;

    for(int u = 0; u < k; u++){

        int currRes = dp[mx-1][u] + dist[node[u]][src];

        res = min(res, currRes);
    }

    if(res >= inf){
        cout << -1 << endl;
        return;
    }

    cout << res << endl;

}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

Submission Info

Judge Result