Submission #2560003
Source Code Expand
#include <bits/stdc++.h> #define r(i,n) for(int i=0;i<n;i++) using namespace std; typedef pair<int,int>P; vector<P>v[100009],rv[100009]; int n,m,t; int d[100009],rd[100009],wei[100009]; void dij1(){ r(i,100009)d[i]=1e9; priority_queue<P,vector<P>,greater<P> >q; q.push(P(0,0)); d[0]=0; while(!q.empty()){ P p=q.top();q.pop(); int now=p.second; int co=p.first; if(d[now]<co)continue; r(i,v[now].size()){ int nex=v[now][i].first; int cost=v[now][i].second+co; if(d[nex]<=cost)continue; d[nex]=cost; q.push(P(cost,nex)); } } } void dij2(){ r(i,100009)rd[i]=1e9; priority_queue<P,vector<P>,greater<P> >q; q.push(P(0,0)); rd[0]=0; while(!q.empty()){ P p=q.top();q.pop(); int now=p.second; int co=p.first; if(rd[now]<co)continue; r(i,rv[now].size()){ int nex=rv[now][i].first; int cost=rv[now][i].second+co; if(rd[nex]<=cost)continue; rd[nex]=cost; q.push(P(cost,nex)); } } } int ans=0; main(){ cin>>n>>m>>t; r(i,n)cin>>wei[i]; r(i,m){ int a,b,c; cin>>a>>b>>c;a--;b--; v[a].push_back(P(b,c)); rv[b].push_back(P(a,c)); } dij1(); dij2(); r(i,n){ int x=t-d[i]-rd[i]; ans=max(ans,x*wei[i]); } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | c7c7 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1337 Byte |
Status | WA |
Exec Time | 133 ms |
Memory | 12416 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 | AC | 3 ms | 5760 KB |
00_example_02.txt | AC | 3 ms | 5760 KB |
00_example_03.txt | AC | 3 ms | 5760 KB |
10_rand_01.txt | WA | 9 ms | 5888 KB |
10_rand_02.txt | WA | 29 ms | 6784 KB |
10_rand_03.txt | WA | 11 ms | 6016 KB |
10_rand_04.txt | WA | 6 ms | 5760 KB |
10_rand_05.txt | WA | 12 ms | 6016 KB |
10_rand_06.txt | WA | 12 ms | 5888 KB |
10_rand_07.txt | WA | 17 ms | 6016 KB |
10_rand_08.txt | WA | 8 ms | 5760 KB |
10_rand_09.txt | WA | 14 ms | 5888 KB |
10_rand_10.txt | WA | 6 ms | 5760 KB |
10_rand_12.txt | WA | 51 ms | 7296 KB |
10_rand_13.txt | WA | 46 ms | 7168 KB |
30_max_01.txt | WA | 104 ms | 9076 KB |
30_max_02.txt | WA | 121 ms | 9488 KB |
30_max_03.txt | AC | 89 ms | 8740 KB |
30_max_04.txt | WA | 133 ms | 10368 KB |
30_max_05.txt | WA | 120 ms | 10368 KB |
30_max_06.txt | WA | 127 ms | 10368 KB |
40_corner_01.txt | WA | 104 ms | 12416 KB |
40_corner_02.txt | WA | 110 ms | 12416 KB |
40_corner_03.txt | WA | 112 ms | 12416 KB |
40_corner_04.txt | WA | 126 ms | 12416 KB |
50_small_01.txt | AC | 4 ms | 5760 KB |
50_small_02.txt | AC | 4 ms | 5760 KB |
50_small_03.txt | WA | 4 ms | 5760 KB |
50_small_04.txt | AC | 4 ms | 5760 KB |
50_small_05.txt | AC | 6 ms | 5760 KB |
50_small_06.txt | AC | 5 ms | 5760 KB |
50_small_07.txt | WA | 4 ms | 5760 KB |
50_small_08.txt | WA | 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 | WA | 3 ms | 5760 KB |
60_hand_03.txt | AC | 3 ms | 5760 KB |
60_hand_04.txt | WA | 3 ms | 5760 KB |
70_max_01.txt | AC | 29 ms | 6656 KB |
70_max_02.txt | AC | 29 ms | 6656 KB |
70_max_03.txt | AC | 30 ms | 6656 KB |