Submission #4658232
Source Code Expand
#include <algorithm> #include <cassert> #include <climits> #include <cmath> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; typedef long long ll; const ll INF = pow(2, 50); const ll MAX_V = 100001; struct edge { ll to, cost; }; typedef pair<ll, ll> P; // firstは最短距離, secondは頂点の番号 vector<edge> G[MAX_V]; ll d[MAX_V]; vector<edge> G_rev[MAX_V]; ll d_rev[MAX_V]; ll N, M, T; vector<ll> A; // 蟻本参照 void dijkstra(ll s) { priority_queue<P, vector<P>, greater<P>> que; fill(d, d + N, INF); d[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); ll v = p.second; if (d[v] < p.first) { continue; } for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } void dijkstra_rev(ll s) { priority_queue<P, vector<P>, greater<P>> que; fill(d_rev, d_rev + N, INF); d_rev[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); ll v = p.second; if (d_rev[v] < p.first) { continue; } for (ll i = 0; i < G_rev[v].size(); i++) { edge e = G_rev[v][i]; if (d_rev[e.to] > d_rev[v] + e.cost) { d_rev[e.to] = d_rev[v] + e.cost; que.push(P(d_rev[e.to], e.to)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> T; A.resize(N); for (ll i = 0; i < N; i++) { cin >> A[i]; } for (ll i = 0; i < M; i++) { ll a, b, c; cin >> a >> b >> c; a--; b--; G[a].push_back(edge{b, c}); G_rev[b].push_back(edge{a, c}); } dijkstra(0); dijkstra_rev(0); ll ans = 0; for (ll i = 0; i < N; i++) { ans = max(ans, A[i] * (T - d[i] - d_rev[i])); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | muras |
Language | C++14 (GCC 5.4.1) |
Score | 50 |
Code Size | 2086 Byte |
Status | WA |
Exec Time | 66 ms |
Memory | 13568 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 0 / 50 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 4 ms | 5760 KB |
00_example_02.txt | AC | 4 ms | 5760 KB |
00_example_03.txt | AC | 4 ms | 5760 KB |
10_rand_01.txt | WA | 6 ms | 6144 KB |
10_rand_02.txt | WA | 15 ms | 7296 KB |
10_rand_03.txt | WA | 7 ms | 6272 KB |
10_rand_04.txt | WA | 4 ms | 5888 KB |
10_rand_05.txt | WA | 7 ms | 6400 KB |
10_rand_06.txt | WA | 7 ms | 6400 KB |
10_rand_07.txt | WA | 9 ms | 6656 KB |
10_rand_08.txt | WA | 5 ms | 6016 KB |
10_rand_09.txt | WA | 8 ms | 6528 KB |
10_rand_10.txt | WA | 5 ms | 5888 KB |
10_rand_12.txt | WA | 29 ms | 8576 KB |
10_rand_13.txt | WA | 26 ms | 8236 KB |
30_max_01.txt | WA | 55 ms | 11880 KB |
30_max_02.txt | WA | 66 ms | 12064 KB |
30_max_03.txt | AC | 43 ms | 11604 KB |
30_max_04.txt | WA | 51 ms | 12672 KB |
30_max_05.txt | WA | 52 ms | 12672 KB |
30_max_06.txt | WA | 51 ms | 12672 KB |
40_corner_01.txt | AC | 43 ms | 13568 KB |
40_corner_02.txt | AC | 46 ms | 13568 KB |
40_corner_03.txt | AC | 46 ms | 13568 KB |
40_corner_04.txt | AC | 47 ms | 13568 KB |
50_small_01.txt | AC | 4 ms | 5888 KB |
50_small_02.txt | AC | 3 ms | 5760 KB |
50_small_03.txt | AC | 4 ms | 5760 KB |
50_small_04.txt | AC | 3 ms | 5760 KB |
50_small_05.txt | AC | 4 ms | 5888 KB |
50_small_06.txt | AC | 4 ms | 5888 KB |
50_small_07.txt | AC | 3 ms | 5760 KB |
50_small_08.txt | AC | 3 ms | 5760 KB |
50_small_09.txt | AC | 4 ms | 5760 KB |
50_small_10.txt | AC | 4 ms | 5760 KB |
60_hand_01.txt | AC | 3 ms | 5760 KB |
60_hand_02.txt | AC | 4 ms | 5760 KB |
60_hand_03.txt | AC | 4 ms | 5760 KB |
60_hand_04.txt | AC | 3 ms | 5760 KB |
70_max_01.txt | AC | 13 ms | 7552 KB |
70_max_02.txt | AC | 13 ms | 7552 KB |
70_max_03.txt | AC | 13 ms | 7552 KB |