備忘録

まとめておきたいことのメモ 主にプロコンのこと

ABC 035 D

今回はこの問題です。

abc035.contest.atcoder.jp

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するまでこんな感じでした。

f:id:usakomachi:20160830150421p:plain

うーんこの。