뉴커우 5차전 A Portal - DP

Face

제목의 뜻

데이터 범위: 1≤n≤300, 1≤m≤40000, 1≤k≤300, 1≤ui, vi≤n, wi≤1 0 9 1\leq n\leq 300, 1\leq m\leq 40000, 1\leq k\leq 300, 1\leq ui, v_i \leq n, w_i \leq 10^9 1≤n≤300,1≤m≤40000,1≤k≤300,1≤ui​,vi​≤n,wi​≤109

선행 기술

Tutorial:

찾기 복잡도 삽입: O (n l o g n) O (nlogn) O (nlogn)

총 복잡도: O(n3)O(n^3)O(n3)

code:

#include 

using namespace std;

#define local
#ifdef local

template<class T>
void _E(T x) { cerr << x; }

void _E(double x) { cerr << fixed << setprecision(6) << x; }

void _E(string s) { cerr << "\"" << s << "\""; }

template<class A, class B>
void _E(pair<A, B> x) {
    cerr << '(';
    _E(x.first);
    cerr << ", ";
    _E(x.second);
    cerr << ")";
}

template<class T>
void _E(vector<T> x) {
    cerr << "[";
    for (auto it = x.begin(); it != x.end(); ++it) {
        if (it != x.begin()) cerr << ", ";
        _E(*it);
    }
    cerr << "]";
}

void ERR() {}

template<class A, class... B>
void ERR(A x, B... y) {
    _E(x);
    cerr << (sizeof...(y) ? ", " : " ");
    ERR(y...);
}

#define debug(x...) do { cerr << "{ "#x" } -> { "; ERR(x); cerr << "}" << endl; } while(false)
#else
#define debug(...) 114514.1919810
#endif
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db long double
#define eps 1e-3
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair
#define pdd pair
#define endl "
"
#define ls ch[now][0]
#define rs ch[now][1]
const ll mod = 998244353;
const ll maxn = 6e2 + 10;


ll qpow(ll a, ll b) {
    ll ret = 1;
    for (; b; a = a * a % mod, b >>= 1) {
        if (b & 1) {
            ret = ret * a % mod;
        }
    }
    return ret;
}

vector<ll> f(maxn), invf(maxn);

ll inv(ll a) {
    return qpow(a, mod - 2);
}

void prework() {
    f[0] = 1;
    _rep(i, 1, maxn - 1) {
        f[i] = f[i - 1] * i % mod;
    }
    invf[maxn - 1] = qpow(f[maxn - 1], mod - 2);
    for (ll i = maxn - 2; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }

}

ll C(ll n, ll m) {
    if (n > m || m < 0)return 0;
    if (n == 0 || m == n) return 1;
    ll res = (f[m] * invf[m - n] % mod * invf[n]) % mod;
    return res;
}

vector<pii > G[maxn];
vector<ll> a;
int n, m, k;

ll g[maxn][maxn], dp[maxn][maxn];


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    met(g, oo);
    met(dp, oo);
    _rep(i, 1, n) {
        g[i][i] = 0;
    }
    _rep(i, 1, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(w, g[u][v]);
    }
    _rep(k, 1, n) {
        _rep(i, 1, n) {
            _rep(j, 1, n) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    k *= 2;
    a.resize(k + 1);
    _rep(i, 1, k) cin >> a[i];
    a[0] = 1;
    dp[0][1] = 0;
    ll res = oo;
    _rep(i, 1, k) {
        _rep(j, 1, n) {
            //           
            dp[i][j] = min(dp[i - 1][j] + min(g[a[i - 1]][a[i]], g[j][a[i]]), dp[i][j]);
            _rep(o, 1, n) { //         
                dp[i][o] = min(dp[i][o],
                               dp[i - 1][j] + min(g[j][o] + g[o][a[i]], g[a[i - 1]][o] + min(g[o][a[i]], g[j][a[i]])));
            }
        }
    }
    _rep(i, 1, n) {
        res = min(res, dp[k][i]);
    }
    cout << res << endl;

}