Submission #678440

#TimeUsernameProblemLanguageResultExecution timeMemory
678440DP_196Relay Marathon (NOI20_relaymarathon)C++14
17 / 100
173 ms2632 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define MASK(i) ((1LL) << (i)) #define all(x) x.begin(), x.end() #define BIT(x, i) ((x) >> (i) & (1LL)) #define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \ << "] = [" ,DBG(__VA_ARGS__) string to_string(const string& s) { return '"' + s + '"'; } void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } template <class T> inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); } template <class T> inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); } const int MAXN = 1e5 + 6; const int INF = 1e9; const int MOD = 1e9 + 7; int n, m, k, a[505], cost[505][505]; struct dat { int v1 = INF, id1 = 0, v2 = INF, id2 = 0; dat (int _v1 = INF, int _id1 = 0, int _v2 = INF, int _id2 = 0) { v1 = _v1, id1 = _id1, v2 = _v2, id2 = _id2; } }; dat best[505]; void solve() { cin >> n >> m >> k; if (n > 500) return; memset(cost, 0x3f, sizeof (cost)); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; minimize(cost[u][v], w); minimize(cost[v][u], w); } for (int i = 1; i <= k; i++) cin >> a[i]; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) minimize(cost[i][j], cost[i][k] + cost[k][j]); for (int i = 1; i <= k; i++) { for (int j = 1; j <= k; j++) { if (i == j) continue; int u = a[i], v = a[j]; if (best[u].v1 >= cost[u][v]) { best[u] = dat(cost[u][v], v, best[u].v1, best[u].id1); } else if (cost[u][v] < best[u].v2) { best[u].v2 = cost[u][v]; best[u].id2 = v; } } } int res = INF; for (int i = 1; i <= k; i++) { for (int j = 1; j <= k; j++) { if (i == j) continue; int u = a[i], v = a[j], sum = INF; if (best[u].id1 != v && best[u].id1 != best[v].id1 && best[v].id1 != u) { minimize(sum, best[u].v1 + best[v].v1); } if (best[u].id1 != v && best[u].id1 != best[v].id2 && best[v].id2 != u) { minimize(sum, best[u].v1 + best[v].v2); } if (best[u].id2 != v && best[u].id2 != best[v].id1 && best[v].id1 != u) { minimize(sum, best[u].v2 + best[v].v1); } if (best[u].id2 != v && best[u].id2 != best[v].id2 && best[v].id2 != u) { minimize(sum, best[u].v2 + best[v].v2); } minimize(res, sum); } } cout << res; } #define TASK "4SPECIAL" int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); int ntest = 1; //cin >> ntest; while (ntest--) solve(); return 0; } //612
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...