ABC 035 D - トレジャーハント ( Dijkstra )

D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder
The key is to observe that only staying in one city will maximize the profit, because if staying in two is better, we will still arrange all time on the higher-price city. We will enumerate which city that will be, and when such city i is fixed, the profit is A[ i ] * ( T - distance_go[ i ] - distance_back[ i ] ). Which can be solved with dijkstra, the dis_back with reversed graph.

int N, M, T;
int A[ MAXN ];
vp G[ MAXN ], rG[ MAXN ];

void solve(){
    cin >> N >> M >> T;
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
    for( int i = 0; i < M; ++i ){
        int a, b, c; cin >> a >> b >> c;
        --a, --b;
        G[ a ].push_back( pii( c, b ) );
        rG[ b ].push_back( pii( c, a ) );
    }

    vi dis_go( N, INF ), dis_back( N, INF );
    priority_queue< pii, vector< pii >, greater< pii > > pq;
    pq.push( pii( dis_go[ 0 ] = 0, 0 ) );
    while( !pq.empty() ){
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if( d != dis_go[ u ] ) continue;
        for( pii p : G[ u ] ){
            int w = p.first;
            int v = p.second;
            if( dis_go[ v ] > d + w )
                pq.push( pii( dis_go[ v ] = d + w, v ) );
        }
    }
    pq.push( pii( dis_back[ 0 ] = 0, 0 ) );
    while( !pq.empty() ){
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if( d != dis_back[ u ] ) continue;
        for( pii p : rG[ u ] ){
            int w = p.first;
            int v = p.second;
            if( dis_back[ v ] > d + w )
                pq.push( pii( dis_back[ v ] = d + w, v ) );
        }
    }

    ll ans = 0;
    for( int i = 0; i < N; ++i )
        ans = max( ans, 1LL * A[ i ] * ( T - dis_go[ i ] - dis_back[ i ] ) );

    cout << ans << "\n";
}