Submission #3005267
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 | Bash (GNU bash v4.3.11) |
Score | 0 |
Code Size | 1672 Byte |
Status | RE |
Exec Time | 6 ms |
Memory | 728 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | RE | 6 ms | 728 KB |
00_example_02.txt | RE | 3 ms | 584 KB |
00_example_03.txt | RE | 3 ms | 584 KB |
10_rand_01.txt | RE | 3 ms | 584 KB |
10_rand_02.txt | RE | 3 ms | 592 KB |
10_rand_03.txt | RE | 3 ms | 592 KB |
10_rand_04.txt | RE | 3 ms | 584 KB |
10_rand_05.txt | RE | 3 ms | 584 KB |
10_rand_06.txt | RE | 3 ms | 592 KB |
10_rand_07.txt | RE | 3 ms | 592 KB |
10_rand_08.txt | RE | 3 ms | 584 KB |
10_rand_09.txt | RE | 3 ms | 584 KB |
10_rand_10.txt | RE | 3 ms | 584 KB |
10_rand_12.txt | RE | 3 ms | 584 KB |
10_rand_13.txt | RE | 3 ms | 584 KB |
30_max_01.txt | RE | 3 ms | 580 KB |
30_max_02.txt | RE | 3 ms | 580 KB |
30_max_03.txt | RE | 3 ms | 580 KB |
30_max_04.txt | RE | 3 ms | 580 KB |
30_max_05.txt | RE | 3 ms | 584 KB |
30_max_06.txt | RE | 3 ms | 584 KB |
40_corner_01.txt | RE | 3 ms | 584 KB |
40_corner_02.txt | RE | 3 ms | 584 KB |
40_corner_03.txt | RE | 3 ms | 584 KB |
40_corner_04.txt | RE | 3 ms | 592 KB |
50_small_01.txt | RE | 3 ms | 584 KB |
50_small_02.txt | RE | 3 ms | 584 KB |
50_small_03.txt | RE | 3 ms | 584 KB |
50_small_04.txt | RE | 3 ms | 584 KB |
50_small_05.txt | RE | 3 ms | 592 KB |
50_small_06.txt | RE | 3 ms | 584 KB |
50_small_07.txt | RE | 3 ms | 592 KB |
50_small_08.txt | RE | 3 ms | 584 KB |
50_small_09.txt | RE | 3 ms | 584 KB |
50_small_10.txt | RE | 3 ms | 584 KB |
60_hand_01.txt | RE | 3 ms | 584 KB |
60_hand_02.txt | RE | 3 ms | 584 KB |
60_hand_03.txt | RE | 3 ms | 584 KB |
60_hand_04.txt | RE | 3 ms | 584 KB |
70_max_01.txt | RE | 3 ms | 584 KB |
70_max_02.txt | RE | 3 ms | 592 KB |
70_max_03.txt | RE | 3 ms | 584 KB |