(ダイクストラ・各頂点からスタート地点までの距離)ABC-035-D-トレジャーハント

問題URL→http://abc035.contest.atcoder.jp/tasks/abc035_d

ある経路で戻ってくるとき、その経路上で最も稼げる町だけに可能な限り滞在すればよいので、滞在する町は1つ。
よってこの滞在する町を全探索する。
この町に滞在できる時間はその町への最短距離を通った時にかかる時間と、帰るのにかかる時間を引いた残りの分。
したがって、ある頂点への最短距離と各頂点からスタート地点への最短距離を求めればいい。
前者は普通のダイクストラでできる。後者はグラフの各辺を逆向きにしてスタート地点からダイクストラをすればよい。

またその町を使うときの行きと帰りの最短経路のうち最も稼げる町の稼げる金額を求めるのにダイクストラに付加情報を作らせる(下コードのMaxValue)
↑実はこれはいらなかった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, M, T;
int A[101010];
int a, b, c;

struct edge
{
    int to, cost;
};

vector<edge> G[101010];
vector<edge> rG[101010];
int d[101010];
int rd[101010];
int maxValue[101010];
int maxValue2[101010];

void dijkstra(int s, vector<edge> GG[], int dd[], int aMaxValue[])
{
    //greater<P>を指定することでfirstが小さい順に取り出せるようにする
    priority_queue<P, vector<P>, greater<P>> que;
    fill(dd, dd + N, INF);
    dd[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (dd[v] < p.first) continue;
        for (edge e : GG[v]) {
            if (dd[e.to] > dd[v] + e.cost) {
                dd[e.to] = dd[v] + e.cost;
                que.push(P(dd[e.to], e.to));
                aMaxValue[e.to] = max(A[e.to], aMaxValue[v]);
            }
        }
    }
}

signed main()
{
    cin >> N >> M >> T;
    REP(i,N) cin >> A[i];
    REP(i,M) {
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(edge{b, c});
        rG[b].push_back(edge{a, c});
    }

    REP(i,N) maxValue[i] = A[i];
    REP(i,N) maxValue2[i] = A[i];

    dijkstra(0, G, d, maxValue);
    dijkstra(0, rG, rd, maxValue2);

    int ans = 0;
    REP(i,N) {
        if (T - d[i] - rd[i] < 0) continue;
        //下の行はいらなかったのでmaxValueを計算する必要はなかった
        //ans = max(ans, (T - d[i] - rd[i]) * max(maxValue[i], maxValue2[i]));
        ans = max(ans, (T - d[i] - rd[i]) * A[i]);
    }
    cout << ans << endl;
}

(2番目の最短経路)POJ-3255-Roadblocks

問題URL→http://poj.org/problem?id=3255

蟻本に載っている問題。
2番目の最短路を求めるにはdistを2つ用意する。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

struct edge
{
    int to;
    int cost;
    
    edge() {}
    edge(int to, int cost) : to(to), cost(cost) {}
};

int N, R;
vector<edge> G[5050];

int dist[5050];     //最短距離
int dist2[5050];    //2番目の最短距離

signed main()
{
    cin >> N >> R;
    REP(i,R) {
        int A, B, D;
        cin >> A >> B >> D;
        A--; B--;
        G[A].push_back(edge(B, D));
        G[B].push_back(edge(A, D));
    }

    //firstが小さい順に取り出せる
    //first:距離 second:頂点番号
    priority_queue<P, vector<P>, greater<P>> que;
    fill(dist, dist + N, INF);
    fill(dist2, dist2 + N, INF);
    dist[0] = 0;
    que.push(P(0, 0));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second, d = p.first;
        if (dist2[v] < d) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            int d2 = d + e.cost;
            if (dist[e.to] > d2) {
                swap(dist[e.to], d2);
                que.push(P(dist[e.to], e.to));
            }
            if (dist2[e.to] > d2 && dist[e.to] < d2) {
                dist2[e.to] = d2;
                que.push(P(dist2[e.to], e.to));
            }
        }
    }

    cout << dist2[N - 1] << endl;
}