BESTSPOT - Vị trí tốt nhất

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<climits>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

#define INF 1000000000
#define N 500
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef pair<int, int> ii;
int favor[N], a[N][N], n, f, c;
vector<vector<ii> > g;

void enter() {
    scanf("%d%d%d",&n,&f,&c);
    for(int i = 0; i < f; favor[i++]--) scanf("%d", favor+i);
    g.resize(n);
    for(int u, v, l, i = 0; i < c; ++i) {
        scanf("%d%d%d",&u,&v,&l);
        g[--u].push_back(ii(--v,l)); g[v].push_back(ii(u,l));
    }
}

void dijkstra(int s, int d[]) {
    REP(u, n) d[u] = INF; d[s] = 0;
    priority_queue<ii, vector<ii>, greater<ii> > q; q.push(ii(0, s));
    while(!q.empty()) {
        int u = q.top().second, du = q.top().first; q.pop();
        if(du > d[u]) continue;
        for(vector<ii>::iterator it = g[u].begin(); it != g[u].end(); ++it) {
            int v = it->first, l = it->second;
            if(du + l < d[v]) q.push(ii(d[v] = du + l, v));
        }
    }
}

void solve() {
    REP(u, n) dijkstra(u, a[u]);
    int mn = INT_MAX, pos = 0;
    REP(i,n) {
        int total = 0;
        for(int j=0; j < f; total += a[i][favor[j++]]);
        if(total < mn) mn = total, pos = i;
    }
    printf("%d\n", pos+1);
}

int main() {
    enter();
    solve();
    return 0;
}

Download