ECNA 2016 - D: Lost in Translation ★★☆☆☆
評価・感想
制約小さくて想定解とは異なる気もするけど、
DAGなら最小有向全域木の1ステップ目で終わるというのが面白かった。
問題
Englishで書かれた本があり、それをnヶ国語に翻訳したい。
m人の翻訳者の候補が居て、i番目の人は言語を言語(またはその逆)にコストで行ってくれる。
Englishから各言語への翻訳ステップを最小化した上で、合計コストの最小値を出力せよ。
codeforces.com
制約
入力例
4 6 Pashto French Amheric Swedish English Pashto 1 English French 1 English Amheric 5 Pashto Amheric 1 Amheric Swedish 5 French Swedish 1
出力例
8
考察・解答
bfs順にしか辿れないようなグラフG'上で最小全域有向木をする。
ただしG'はDAGなので、最小全域有向木の0.5ステップくらいで終わる(sccしない)。
つまり、G'上のEnglish以外の各頂点について、
そこに入る辺の中からコスト最小の辺を1つずつ選んだグラフは
閉路を持たないから解である。
プログラム
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> P; #define EACH(i,a) for (auto&& i : a) #define FOR(i,a,b) for (ll i=(a);i<(b);++i) #define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);--i) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) #define __GET_MACRO3(_1,_2,_3,NAME,...) NAME #define rep(...) __GET_MACRO3(__VA_ARGS__,FOR,REP)(__VA_ARGS__) #define rrep(...) __GET_MACRO3(__VA_ARGS__,RFOR,RREP)(__VA_ARGS__) #define pb push_back #define ALL(a) (a).begin(),(a).end() #define chmin(x,v) x = min(x,v) #define chmax(x,v) x = max(x,v) const ll linf = 1e18; const int inf = 1e9; const double eps = 1e-12; const double pi = acos(-1); template<typename T> istream& operator>>(istream& is, vector<T>& vec) { EACH(x,vec) is >> x; return is; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { rep(i,vec.size()) { if (i) os << " "; os << vec[i]; } return os; } struct Edge { ll to, cost; }; vector<ll> bfs(const vector<vector<Edge>>& G, const ll s) { const ll n = G.size(); vector<ll> res(n, -1); res[s] = 0; queue<ll> Q; Q.push(s); while ( !Q.empty() ) { ll v = Q.front(); Q.pop(); EACH(e, G[v]) { if (res[e.to] < 0) { res[e.to] = res[v]+1; Q.push(e.to); } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n, m; cin >> n >> m; vector<string> name(n); cin >> name; name.insert(name.begin(), "English"); ++n; map<string, ll> tbl; rep(i, n) { tbl[name[i]] = i; } vector<vector<Edge>> G(n); rep(i, m) { string a, b; ll c; cin >> a >> b >> c; ll from = tbl[a]; ll to = tbl[b]; G[from].pb({to, c}); G[to].pb({from, c}); } vector<ll> dist = bfs(G, 0); try { rep(i, n) { if (dist[i] < 0) throw 1; } ll ans = 0; rep(i, 1, n) { ll c = linf; EACH(e, G[i]) { if (dist[e.to]+1 == dist[i]) { c = min(c, e.cost); } } assert(c < linf); ans += c; } cout << ans << endl; } catch (int err) { cout << "Impossible" << endl; } }