# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
854232 |
2023-09-26T12:03:48 Z |
LeVanThuc |
Robot (JOI21_ho_t4) |
C++17 |
|
811 ms |
125384 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
if(x<y)
{
x=y;
return 1;
}
return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
if(x>y)
{
x=y;
return 1;
}
return 0;
}
void online()
{
std::ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef thuc
freopen("input.INP","r",stdin);
freopen("output.OUT","w",stdout);
#endif
}
const ll N=2e5+10,inf=1e18;
map<ll,vector<pll> > gr[N];
map<ll,ll> f1[N],sum[N],vs[N];
ll f[N];
ll n,m;
struct info
{
ll d,u,s;
info(ll _d=0,ll _u=0,ll _s=0)
{
d=_d;
u=_u;
s=_s;
}
bool operator <(const info &o) const
{
return d>o.d;
}
};
int main()
{
online();
cin>>n>>m;
for(int i=1; i<=m; i++)
{
ll u,v,c,s;
cin>>u>>v>>c>>s;
gr[u][c].emplace_back(v,s);
gr[v][c].emplace_back(u,s);
sum[u][c]+=s;
sum[v][c]+=s;
}
priority_queue<info> qq;
memset(f,0x3f,sizeof f);
f[1]=0;
qq.emplace(0,1,0);
while(qq.size())
{
auto [d,u,s]=qq.top();
qq.pop();
if(!s)
{
if(d!=f[u]) continue;
for(auto &[c,adj]:gr[u])
{
for(auto [v,w]:adj)
{
if(minimize(f[v],f[u]+sum[u][c]-w))
{
qq.emplace(f[v],v,0);
}
if(minimize(f[v],f[u]+w))
{
qq.emplace(f[v],v,0);
}
if(vs[v][c]==0||minimize(f1[v][c],f[u]))
{
vs[v][c]=1;
f1[v][c]=f[u];
qq.emplace(f1[v][c],v,c);
}
}
}
}
else
{
if(d!=f1[u][s]) continue;
ll c=s;
for(auto [v,w]:gr[u][s])
{
if(minimize(f[v],f1[u][s]+sum[u][c]-w))
{
qq.emplace(f[v],v,0);
}
}
}
}
if(f[n]>1e18) f[n]=-1;
cout<<f[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
39512 KB |
Output is correct |
2 |
Correct |
8 ms |
39516 KB |
Output is correct |
3 |
Correct |
8 ms |
39516 KB |
Output is correct |
4 |
Correct |
8 ms |
39420 KB |
Output is correct |
5 |
Correct |
8 ms |
39648 KB |
Output is correct |
6 |
Correct |
8 ms |
39516 KB |
Output is correct |
7 |
Correct |
8 ms |
39696 KB |
Output is correct |
8 |
Correct |
8 ms |
39516 KB |
Output is correct |
9 |
Correct |
11 ms |
40284 KB |
Output is correct |
10 |
Correct |
12 ms |
40280 KB |
Output is correct |
11 |
Correct |
9 ms |
40028 KB |
Output is correct |
12 |
Correct |
10 ms |
40280 KB |
Output is correct |
13 |
Correct |
9 ms |
39852 KB |
Output is correct |
14 |
Correct |
9 ms |
40028 KB |
Output is correct |
15 |
Correct |
9 ms |
39772 KB |
Output is correct |
16 |
Correct |
9 ms |
40032 KB |
Output is correct |
17 |
Correct |
9 ms |
40036 KB |
Output is correct |
18 |
Correct |
9 ms |
39772 KB |
Output is correct |
19 |
Correct |
9 ms |
39772 KB |
Output is correct |
20 |
Correct |
9 ms |
39812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
63336 KB |
Output is correct |
2 |
Correct |
76 ms |
51896 KB |
Output is correct |
3 |
Correct |
131 ms |
58120 KB |
Output is correct |
4 |
Correct |
92 ms |
55308 KB |
Output is correct |
5 |
Correct |
811 ms |
121536 KB |
Output is correct |
6 |
Correct |
603 ms |
110264 KB |
Output is correct |
7 |
Correct |
298 ms |
91200 KB |
Output is correct |
8 |
Correct |
346 ms |
81880 KB |
Output is correct |
9 |
Correct |
339 ms |
81492 KB |
Output is correct |
10 |
Correct |
321 ms |
78820 KB |
Output is correct |
11 |
Correct |
99 ms |
57268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
39512 KB |
Output is correct |
2 |
Correct |
8 ms |
39516 KB |
Output is correct |
3 |
Correct |
8 ms |
39516 KB |
Output is correct |
4 |
Correct |
8 ms |
39420 KB |
Output is correct |
5 |
Correct |
8 ms |
39648 KB |
Output is correct |
6 |
Correct |
8 ms |
39516 KB |
Output is correct |
7 |
Correct |
8 ms |
39696 KB |
Output is correct |
8 |
Correct |
8 ms |
39516 KB |
Output is correct |
9 |
Correct |
11 ms |
40284 KB |
Output is correct |
10 |
Correct |
12 ms |
40280 KB |
Output is correct |
11 |
Correct |
9 ms |
40028 KB |
Output is correct |
12 |
Correct |
10 ms |
40280 KB |
Output is correct |
13 |
Correct |
9 ms |
39852 KB |
Output is correct |
14 |
Correct |
9 ms |
40028 KB |
Output is correct |
15 |
Correct |
9 ms |
39772 KB |
Output is correct |
16 |
Correct |
9 ms |
40032 KB |
Output is correct |
17 |
Correct |
9 ms |
40036 KB |
Output is correct |
18 |
Correct |
9 ms |
39772 KB |
Output is correct |
19 |
Correct |
9 ms |
39772 KB |
Output is correct |
20 |
Correct |
9 ms |
39812 KB |
Output is correct |
21 |
Correct |
161 ms |
63336 KB |
Output is correct |
22 |
Correct |
76 ms |
51896 KB |
Output is correct |
23 |
Correct |
131 ms |
58120 KB |
Output is correct |
24 |
Correct |
92 ms |
55308 KB |
Output is correct |
25 |
Correct |
811 ms |
121536 KB |
Output is correct |
26 |
Correct |
603 ms |
110264 KB |
Output is correct |
27 |
Correct |
298 ms |
91200 KB |
Output is correct |
28 |
Correct |
346 ms |
81880 KB |
Output is correct |
29 |
Correct |
339 ms |
81492 KB |
Output is correct |
30 |
Correct |
321 ms |
78820 KB |
Output is correct |
31 |
Correct |
99 ms |
57268 KB |
Output is correct |
32 |
Correct |
96 ms |
53616 KB |
Output is correct |
33 |
Correct |
115 ms |
57292 KB |
Output is correct |
34 |
Correct |
353 ms |
83092 KB |
Output is correct |
35 |
Correct |
267 ms |
72704 KB |
Output is correct |
36 |
Correct |
286 ms |
78276 KB |
Output is correct |
37 |
Correct |
320 ms |
82392 KB |
Output is correct |
38 |
Correct |
301 ms |
91024 KB |
Output is correct |
39 |
Correct |
109 ms |
57316 KB |
Output is correct |
40 |
Correct |
375 ms |
82860 KB |
Output is correct |
41 |
Correct |
372 ms |
82912 KB |
Output is correct |
42 |
Correct |
462 ms |
94244 KB |
Output is correct |
43 |
Correct |
206 ms |
65068 KB |
Output is correct |
44 |
Correct |
337 ms |
71864 KB |
Output is correct |
45 |
Correct |
259 ms |
78160 KB |
Output is correct |
46 |
Correct |
246 ms |
78344 KB |
Output is correct |
47 |
Correct |
308 ms |
82016 KB |
Output is correct |
48 |
Correct |
801 ms |
125384 KB |
Output is correct |