| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55162 |
2018-07-06T07:29:05 Z |
노영훈(#1526) |
None (JOI14_ho_t4) |
C++11 |
|
400 ms |
14580 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const int MX=100010, inf=2e9;
const ll linf=2e17;
int n, m, h0, H[MX];
vector<pii> G[MX];
ll S[MX];
ll ans=linf;
void gozero(){
ll D[MX];
priority_queue<pli, vector<pli>, greater<pli>> Q;
for(int i=1; i<=n; i++) D[i]=linf;
D[1]=0; Q.push({0,1});
while(!Q.empty()){
int v=Q.top().second; ll d=Q.top().first; Q.pop();
if(D[v]!=d) continue;
for(pii &p:G[v]){
int x,c; tie(x,c)=p;
ll now=d+c;
if(h0-now<0) continue;
if(h0-now>H[x]) now=h0-H[x];
if(now>=D[x]) continue;
D[x]=now; Q.push({now,x});
}
}
if(D[n]<=h0) ans=D[n]+H[n]-(h0-D[n]);
for(int i=1; i<=n; i++) S[i]=linf;
for(int i=1; i<=n; i++){
if(h0<D[i]) continue;
S[i]=min(S[i], D[i] + (h0-D[i]));
for(pii &e:G[i]){
int x,c; tie(x,c)=e;
S[x]=min(S[x], D[i] + abs(h0-D[i]-c) + c);
}
}
if(S[n]<linf) ans=min(ans, S[n]+H[n]);
// for(int i=1; i<=n; i++) cout<<S[i]<<' ';
// cout<<'\n';
}
ll solve(){
ll D[MX];
priority_queue<pli, vector<pli>, greater<pli>> Q;
for(int i=1; i<=n; i++) D[i]=linf;
for(int i=1; i<=n; i++)
if(S[i]<linf) D[i]=S[i], Q.push({D[i], i});
while(!Q.empty()){
int v=Q.top().second; ll d=Q.top().first; Q.pop();
if(D[v]!=d) continue;
for(pii &e:G[v]){
int x,c; tie(x,c)=e; c*=2;
if(D[v]+c>=D[x]) continue;
D[x]=D[v]+c; Q.push({D[x], x});
}
}
// for(int i=1; i<=n; i++) cout<<D[i]<<' ';
// cout<<'\n';
return D[n]+H[n];
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>h0;
for(int i=1; i<=n; i++) cin>>H[i];
for(int i=1; i<=m; i++){
int u, v, c; cin>>u>>v>>c;
if(H[u]-c>=0) G[u].push_back({v,c});
if(H[v]-c>=0) G[v].push_back({u,c});
}
gozero();
ans=min(ans, solve());
cout<<(ans>=linf ? -1 : ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2952 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2980 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2980 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2980 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2980 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 9 |
Correct |
7 ms |
2980 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2992 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3120 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3144 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
7832 KB |
Output is correct |
| 2 |
Correct |
165 ms |
12724 KB |
Output is correct |
| 3 |
Correct |
122 ms |
12724 KB |
Output is correct |
| 4 |
Correct |
241 ms |
13384 KB |
Output is correct |
| 5 |
Correct |
212 ms |
13384 KB |
Output is correct |
| 6 |
Correct |
13 ms |
13384 KB |
Output is correct |
| 7 |
Correct |
182 ms |
13384 KB |
Output is correct |
| 8 |
Correct |
400 ms |
13384 KB |
Output is correct |
| 9 |
Correct |
186 ms |
13384 KB |
Output is correct |
| 10 |
Correct |
80 ms |
13384 KB |
Output is correct |
| 11 |
Correct |
32 ms |
13384 KB |
Output is correct |
| 12 |
Correct |
154 ms |
13384 KB |
Output is correct |
| 13 |
Correct |
60 ms |
13384 KB |
Output is correct |
| 14 |
Correct |
137 ms |
13384 KB |
Output is correct |
| 15 |
Correct |
8 ms |
13384 KB |
Output is correct |
| 16 |
Correct |
143 ms |
13384 KB |
Output is correct |
| 17 |
Correct |
37 ms |
13384 KB |
Output is correct |
| 18 |
Correct |
26 ms |
13384 KB |
Output is correct |
| 19 |
Correct |
60 ms |
13384 KB |
Output is correct |
| 20 |
Correct |
33 ms |
13384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2952 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2980 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2980 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2980 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2980 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 8 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 9 |
Correct |
7 ms |
2980 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2980 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2992 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3120 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3144 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3144 KB |
Output is correct |
| 21 |
Correct |
170 ms |
7832 KB |
Output is correct |
| 22 |
Correct |
165 ms |
12724 KB |
Output is correct |
| 23 |
Correct |
122 ms |
12724 KB |
Output is correct |
| 24 |
Correct |
241 ms |
13384 KB |
Output is correct |
| 25 |
Correct |
212 ms |
13384 KB |
Output is correct |
| 26 |
Correct |
13 ms |
13384 KB |
Output is correct |
| 27 |
Correct |
182 ms |
13384 KB |
Output is correct |
| 28 |
Correct |
400 ms |
13384 KB |
Output is correct |
| 29 |
Correct |
186 ms |
13384 KB |
Output is correct |
| 30 |
Correct |
80 ms |
13384 KB |
Output is correct |
| 31 |
Correct |
32 ms |
13384 KB |
Output is correct |
| 32 |
Correct |
154 ms |
13384 KB |
Output is correct |
| 33 |
Correct |
60 ms |
13384 KB |
Output is correct |
| 34 |
Correct |
137 ms |
13384 KB |
Output is correct |
| 35 |
Correct |
8 ms |
13384 KB |
Output is correct |
| 36 |
Correct |
143 ms |
13384 KB |
Output is correct |
| 37 |
Correct |
37 ms |
13384 KB |
Output is correct |
| 38 |
Correct |
26 ms |
13384 KB |
Output is correct |
| 39 |
Correct |
60 ms |
13384 KB |
Output is correct |
| 40 |
Correct |
33 ms |
13384 KB |
Output is correct |
| 41 |
Correct |
107 ms |
13384 KB |
Output is correct |
| 42 |
Correct |
41 ms |
13384 KB |
Output is correct |
| 43 |
Correct |
84 ms |
13384 KB |
Output is correct |
| 44 |
Correct |
93 ms |
13384 KB |
Output is correct |
| 45 |
Correct |
176 ms |
13384 KB |
Output is correct |
| 46 |
Correct |
16 ms |
13384 KB |
Output is correct |
| 47 |
Correct |
200 ms |
14580 KB |
Output is correct |
| 48 |
Correct |
197 ms |
14580 KB |
Output is correct |
| 49 |
Correct |
188 ms |
14580 KB |
Output is correct |
| 50 |
Correct |
300 ms |
14580 KB |
Output is correct |
| 51 |
Correct |
40 ms |
14580 KB |
Output is correct |
| 52 |
Correct |
236 ms |
14580 KB |
Output is correct |
| 53 |
Correct |
126 ms |
14580 KB |
Output is correct |
| 54 |
Correct |
127 ms |
14580 KB |
Output is correct |
| 55 |
Correct |
164 ms |
14580 KB |
Output is correct |
| 56 |
Correct |
222 ms |
14580 KB |
Output is correct |
| 57 |
Correct |
76 ms |
14580 KB |
Output is correct |
| 58 |
Correct |
8 ms |
14580 KB |
Output is correct |
| 59 |
Correct |
100 ms |
14580 KB |
Output is correct |
| 60 |
Correct |
58 ms |
14580 KB |
Output is correct |
