ABC 035 D
今回はこの問題です。
n箇所の町をつなぐ道がm本あります。それぞれの道について、町aから町bへc分をかけて移動することができます(反対方向には移動できません)。またそれぞれの町について、1分滞在するごとにお金をA[i]だけ手に入れられます。高橋君はトレジャーハントに出かけることにしました。高橋君は時刻0のとき町1を出発し、T分後に町1に帰ってこないといけません。このとき、高橋君が得ることのできるお金の最大値を求めなさい、という問題です。
町1を出発→町i(2<=i<=n)に到着、滞在→町1に帰る、という場合のみ考えればいいです。寄り道してても得られるお金は最大値になりえません。もっとお金が得られる町に寄り道するというのなら、最初からその町に向かえばいいじゃんという話です。
そこで、それぞれの町について町1からその町へ向かうのにかかる最短時間と、その町から町1へ帰るのにかかる最短時間を求めます。余った時間はすべてその町で滞在するものとします。これで得られるお金がわかるので、その最大値を求めればいいです。
行き道と帰り道が異なるので、別々にダイクストラ法で最短距離を求めます。帰り道を求めるとき、それぞれの町から町1の通路を求めると、ダイクストラ法をn回実行することになるので時間がかかり過ぎてしまいます。そこで、入力された通路についてaとb、つまり出発点と到着点を入れ替えたものも記憶しておきます。すべての道を逆向きにしておけば、町1からそれぞれの道を求めればそれが帰り道になります。
回答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int main() { long long int n, m, t; cin >> n >> m >> t; long long int money[100001]; for(int i = 1; i <= n; i++){ cin >> money[i]; } vector<vector<pair<long long int, long long int> > > ikiroad(100001), kaeriroad(100001); for(int i = 0; i < m; i++){ long long int a, b, c; cin >> a >> b >> c; ikiroad[a].push_back(make_pair(b, c)); kaeriroad[b].push_back(make_pair(a, c)); } long long int iki[100001]; long long int kaeri[100001]; for(int i = 1; i <= n; i++){ iki[i] = mod; kaeri[i] = mod; } iki[1] = 0; kaeri[1] = 0; priority_queue<pair<long long int, long long int> > qu; qu.push(make_pair((long long int)0, 1)); while(!qu.empty()){ long long int nowplace = (qu.top()).second; long long int nowtime = (qu.top()).first; qu.pop(); if(iki[nowplace] < -nowtime) continue; iki[nowplace] = -nowtime; // cout << nowplace << " " << nowtime << endl; for(int i = 0; i < ikiroad[nowplace].size(); i++){ long long int nextplace = ikiroad[nowplace][i].first; long long int cost = ikiroad[nowplace][i].second; qu.push(make_pair(nowtime - cost, nextplace)); } } qu.push(make_pair((long long int)0, 1)); while(!qu.empty()){ long long int nowplace = (qu.top()).second; long long int nowtime = (qu.top()).first; qu.pop(); if(kaeri[nowplace] < -nowtime) continue; kaeri[nowplace] = -nowtime; // cout << nowplace << " " << nowtime << endl; for(int i = 0; i < kaeriroad[nowplace].size(); i++){ long long int nextplace = kaeriroad[nowplace][i].first; long long int cost = kaeriroad[nowplace][i].second; qu.push(make_pair(nowtime - cost, nextplace)); } } long long int ans = money[1] * t; for(int i = 2; i <= n; i++){ ans = max(ans, money[i] * max((long long int)0, t - iki[i] - kaeri[i])); } cout << ans << endl; return 0; }
ダイクストラ二回書いたのは頭悪いですね。汚いコードだ。
ちなみにACするまでこんな感じでした。
うーんこの。