Cod sursa(job #2619813)

Utilizator RobertLearnsCDragomir Robert. RobertLearnsC Data 28 mai 2020 13:43:27
Problema Ubuntzei Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <bits/stdc++.h>
using namespace std;

vector <pair<int, int> > graph[2005];
int n, m, k, loc[2005], dist[2005], dp[2005][2005], ans[2005][2005];
queue <int> q;

void prepDijkstra(int source) {
    for(int i = 0; i <= n; i++) {
        dist[i] = 99999999;
    }
    dist[source] = 0;
}

void dijkstra(int source) {
    q.push(source);
    while(q.size()) {
        int currNode = q.front(); q.pop();
        for(int i = 0; i < graph[currNode].size(); ++i) {
            pair <int, int> neighbour = graph[currNode][i];
            if(dist[neighbour.first] > dist[currNode] + neighbour.second) {
                dist[neighbour.first] = dist[currNode] + neighbour.second;
                q.push(neighbour.first);
            }
        }
    }
}

int main() {
    freopen("ubuntzei.in", "r", stdin);
    freopen("ubuntzei.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; ++i) {
        scanf("%d", &loc[i]);
    }
    loc[0] = 1, loc[k + 1] = n;

    for(int i = 1; i <= m; ++i) {
        int x, y, val;
        scanf("%d%d%d", &x, &y, &val);
        graph[x].push_back({y, val});
        graph[y].push_back({x, val});
    }

    for(int i = 0; i <= k + 1; i++) {
        prepDijkstra(loc[i]);
        dijkstra(loc[i]);
        for(int j = 0; j <= k + 1; j++) {
            dp[i][j] = dist[loc[j]];
        }
    }

    for(int i = 0; i <= (1 << k); i++) {
        for(int j = 0; j <= k; j++) {
            (!i && !j) ? ans[i][j] = 0 : ans[i][j] = 99999999;
        }
    }

    for(int i = 0; i < (1 << k); i++) {
        for(int j = 0; j < k; j++) {
            if(i & (1 << j)) {
                for(int ind = 0; ind <= k; ind++) {
                    ans[i][j + 1] = min(ans[i][j + 1], ans[(i - (1 << j))][ind] + dp[ind][j + 1]);
                }
            }
        }
    }

    int minLength = 99999999;
    for(int i = 1; i <= k; i++) {
        minLength = min(minLength, ans[(1 << k) - 1][i] + dp[i][k + 1]);
    }

    printf("%d", minLength);
}