Submission #3005269
Source Code Expand
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <string> #include <set> #include <map> #define REP(i,n) for(ll i = 0; i < (ll)n; i++) #define INF 1000000000000000 using namespace std; typedef long long ll; typedef double db; typedef string str; struct edge{ll to, cost;}; typedef pair<ll,ll> P; struct graph{ ll V; vector<vector<edge> > G; vector<ll> d; graph(ll n){ init(n); } void init(ll n){ V = n; G.resize(V); d.resize(V); REP(i,V){ d[i] = INF; } } void add_edge(ll s, ll t, ll cost){ edge e; e.to = t, e.cost = cost; G[s].push_back(e); } void dijkstra(ll s){ REP(i,V){ d[i] = INF; } d[s] = 0; priority_queue<P,vector<P>, greater<P> > que; 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(auto e : G[v]){ if(d[e.to]>d[v]+e.cost){ d[e.to] = d[v]+e.cost; que.push(P(d[e.to],e.to)); } } } } }; int main(){ ll n,m,t; cin >> n >> m >> t; ll a[n]; graph g1(n); //順方向グラフ graph g2(n); //逆方向グラフ REP(i,n){ cin >> a[i]; } REP(i,m){ ll a,b,c; cin >> a >> b >> c; g1.add_edge(a-1,b-1,c); g2.add_edge(b-1,a-1,c); } g1.dijkstra(0); g2.dijkstra(0); ll ans = 0; REP(i,n){ if(t<g1.d[i]+g2.d[i]) continue; ll money = a[i]*(t-g1.d[i]-g2.d[i]); ans = max(money, ans); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | nexusuica |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1672 Byte |
Status | AC |
Exec Time | 125 ms |
Memory | 13568 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 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 | 1 ms | 256 KB |
00_example_02.txt | AC | 1 ms | 256 KB |
00_example_03.txt | AC | 1 ms | 256 KB |
10_rand_01.txt | AC | 7 ms | 1536 KB |
10_rand_02.txt | AC | 28 ms | 2816 KB |
10_rand_03.txt | AC | 9 ms | 1792 KB |
10_rand_04.txt | AC | 3 ms | 896 KB |
10_rand_05.txt | AC | 11 ms | 2432 KB |
10_rand_06.txt | AC | 10 ms | 2944 KB |
10_rand_07.txt | AC | 16 ms | 4480 KB |
10_rand_08.txt | AC | 6 ms | 1792 KB |
10_rand_09.txt | AC | 14 ms | 3840 KB |
10_rand_10.txt | AC | 4 ms | 1024 KB |
10_rand_12.txt | AC | 51 ms | 3844 KB |
10_rand_13.txt | AC | 46 ms | 3628 KB |
30_max_01.txt | AC | 105 ms | 7400 KB |
30_max_02.txt | AC | 125 ms | 8736 KB |
30_max_03.txt | AC | 87 ms | 6400 KB |
30_max_04.txt | AC | 124 ms | 12544 KB |
30_max_05.txt | AC | 122 ms | 12672 KB |
30_max_06.txt | AC | 120 ms | 12544 KB |
40_corner_01.txt | AC | 103 ms | 13568 KB |
40_corner_02.txt | AC | 111 ms | 13568 KB |
40_corner_03.txt | AC | 111 ms | 13568 KB |
40_corner_04.txt | AC | 116 ms | 13568 KB |
50_small_01.txt | AC | 2 ms | 384 KB |
50_small_02.txt | AC | 1 ms | 256 KB |
50_small_03.txt | AC | 1 ms | 256 KB |
50_small_04.txt | AC | 1 ms | 256 KB |
50_small_05.txt | AC | 3 ms | 384 KB |
50_small_06.txt | AC | 2 ms | 384 KB |
50_small_07.txt | AC | 1 ms | 256 KB |
50_small_08.txt | AC | 1 ms | 256 KB |
50_small_09.txt | AC | 2 ms | 256 KB |
50_small_10.txt | AC | 1 ms | 256 KB |
60_hand_01.txt | AC | 1 ms | 256 KB |
60_hand_02.txt | AC | 1 ms | 256 KB |
60_hand_03.txt | AC | 1 ms | 256 KB |
60_hand_04.txt | AC | 1 ms | 256 KB |
70_max_01.txt | AC | 27 ms | 2048 KB |
70_max_02.txt | AC | 27 ms | 2048 KB |
70_max_03.txt | AC | 27 ms | 2048 KB |