Shortcut (USACO Gold 2019 January)

Shortcut (USACO Gold 2019 January)

这个题的基本意思，是在图上加一条边，求能够节省从各个点回到1这个点的牛的总路径长度的最大值。有两个关键条件：

  1. 路径长度相同的时候，要选字母序靠前的路径。
  2. 新增的边只有当牛走原来路径能碰上的时候，才能节省距离。

条件2的意思，就是新增边之后用标准方法求最短路的办法是不对的，需要另想办法。条件1的意思，是求最短路的时候需要仔细选择方案。

既然是最短路径，最直观的办法当然还是从Dijkstra开始，我们沿这个往下想，发现是可以找到比较直观的方法的：

  1. 对每个点，算出最短距离，以及经过这个点的牛的数量，如果shortcut从这里出发（到节点1），则节省的数值可以得到。
  2. 得到每个点经过牛的数量的办法：每个点保存最短路的第一步走到哪里，如果有几条，就保存目标点编号最小的（这样就保证了最短路径是字母序最前的）。
  3. 然后对所有牛走一遍最短路，累加牛的数量就得到每个点牛经过的数量，结合最短距离，就可以找到最多节省的距离。

最后的复杂度是O(n2)\mathcal{O}(n^2)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
int n, m, T;
int c[10005];           // c[i] <= 1e4
vector<pii> adj[10005]; // target, time (<=25000)
int dist[10005];
int nxt[10005];         // first step in shortest path
int cows[10005];        // # of cows walking over i
 
int main() {
    scanf("%d %d %d", &n, &m, &T);
    for (int i = 0; i < n; i++)
        scanf("%d", &c[i]);
    for (int i = 0; i < m; i++) {
        int u,v,t;
        scanf("%d %d %d", &u, &v, &t);
        u--; v--;
        adj[u].push_back({v, t});
        adj[v].push_back({u, t});
    }
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0,0});
    fill(dist, dist+n, 1e9);
    dist[0] = 0;
    while (!q.empty()) {        // dijkstra
        int u = q.top().second, du = q.top().first;
        q.pop();
        if (du != dist[u]) continue;
        for (auto p: adj[u]) {
            int v = p.first, dv = p.second;
            int d = dist[u] + dv;
            if (d < dist[v] || d == dist[v] && u < nxt[v]) {
                dist[v] = d;
                nxt[v] = u;
                q.push({d, v});
            }
        }
    }
    for (int i = 1; i < n; i++) {   // calc cows over each field
        for (int j = i; j != 0; j = nxt[j])
            cows[j] += c[i];
    }
    ll ans = 0;
    for (int i = 1; i < n; i++) {   // find best field
        ans = max(ans, (ll)cows[i] * (dist[i] - T));
    }
    printf("%lld", ans);
    return 0;
}