Submission #677414

---

Source Code Expand

#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;

int main() {
  int n, m, t;
  cin >> n >> m >> t;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  adjacency_list<listS, vecS, directedS, no_property, property<edge_weight_t, long long>> graph1(n), graph2(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    add_edge(a, b, c, graph1);
    add_edge(b, a, c, graph2);
  }

  vector<long long> distances1(n), distances2(n);
  vector<int> parents1(n), parents2(n);
  dijkstra_shortest_paths(graph1, 0, distance_map(distances1.data()).predecessor_map(parents1.data()));
  dijkstra_shortest_paths(graph2, 0, distance_map(distances2.data()).predecessor_map(parents2.data()));

  long long res = 0;
  for (int i = 0; i < n; ++i) {
    if (i != 0 && (parents1[i] == i || parents2[i] == i)) continue;
    res = max(res, a[i] * (t - distances1[i] - distances2[i]));
  }
  cout << res << endl;
}

Submission Info

Judge Result