/* http://usaco.org/index.php?page=viewproblem2&cpid=491 (create a free account) USACO 2014 December Silver Ques. 1: Piggyback This code is not for Sololearn, I recommend onlinegdb.com or visual studio code Make a file named paint.in and put in: 4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8 Output: 22 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include #include #include #include #include using namespace std; typedef long long ll; vector > fields; ll b, e, p, n, m; vector find_dst(int start){ vector visited; visited.resize(n + 1, 0); deque queue; queue.push_back(start); vector result; result.resize(n + 1, 0); while (queue.size() > 0){ int q = queue.front(); queue.pop_front(); if(!(visited[q])){ visited[q] = 1; } for(int i; i < fields[q].size();i++){ if(!(visited[fields[q][i]]) && find(queue.begin(), queue.end(), fields[q][i]) == queue.end()){ queue.push_back(fields[q][i]); result[fields[q][i]] = result[q] + 1; } } } return result; } int main(){ ifstream fin("piggyback.in"); ofstream fout("piggyback.out"); fin >> b >> e >> p >> n >> m; fields.resize(n + 1); for (int i = 0; i < m; i++){ int farm1, farm2; fin >> farm1 >> farm2; fields[farm1].push_back(farm2); fields[farm2].push_back(farm1); } vector dist_b = find_dst(1); vector dist_e = find_dst(2); vector dist_n = find_dst(n); ll result = LLONG_MAX; for(int i = 1; i < n + 1; i++){ ll tmp = dist_b[i] * b + dist_e[i] * e + dist_n[i] * p; if (result > tmp){ result = tmp; } } fout << result << endl; fout.close(); fin.close(); return 0; }

USACO #22: Piggyback C++