# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
474769 |
2021-09-19T15:50:16 Z |
nguot |
Robot (JOI21_ho_t4) |
C++14 |
|
1069 ms |
87792 KB |
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0)
#define int long long
const int N = 1e5+10;
map<int,int> f2[N],d[N];
int f1[N],n,m;
struct edge
{
int to,c,w;
};
map<int,vector<edge> > ke[N];
main()
{
fasty;
//freopen("task.inp","r",stdin);
cin>>n>>m;
fori(i,1,m)
{
int u,v,w,c;
cin>>u>>v>>c>>w;
d[u][c]+=w;
d[v][c]+=w;
ke[u][c].pb({v,c,w});
ke[v][c].pb({u,c,w});
}
memset(f1,0x3f,sizeof(f1));
f1[1] = 0;
priority_queue<pair<int,ii> > h;
h.push({0,{1,0}});
//f2[umin][c] : (di vao u = c hoac di ra u cung = c)
while(!h.empty())
{
int dmin,umin,c;
tie(umin,c) = h.top().se;
dmin = -h.top().fi;
h.pop();
if(c)
{
if(f2[umin][c]!=dmin) continue;
forv(v,ke[umin][c])
{
if(f1[v.to] > dmin + d[umin][c] - v.w)
{
f1[v.to] = dmin + d[umin][c] - v.w;
h.push({-f1[v.to],{v.to,0}});
}
}
}
else
{
if(f1[umin]!=dmin) continue;
forv(i,ke[umin]) forv(j,i.se)
{
if(f1[j.to] > dmin + d[umin][j.c] - j.w)
{
f1[j.to] = dmin + d[umin][j.c] - j.w;
h.push({-f1[j.to],{j.to,0}});
}
if(f1[j.to] > dmin + j.w)
{
f1[j.to] = dmin + j.w;
h.push({-f1[j.to],{j.to,0}});
}
if(!f2[j.to].count(j.c) || (f2[j.to][j.c] > dmin))
{
f2[j.to][j.c] = dmin;
h.push({-f2[j.to][j.c],{j.to,j.c}});
}
}
}
}
cout<<(f1[n]==f1[0] ? -1 : f1[n]);
}
Compilation message
Main.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
33 | main()
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15180 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
9 ms |
15092 KB |
Output is correct |
4 |
Correct |
9 ms |
15180 KB |
Output is correct |
5 |
Correct |
9 ms |
15180 KB |
Output is correct |
6 |
Correct |
9 ms |
15180 KB |
Output is correct |
7 |
Correct |
10 ms |
15324 KB |
Output is correct |
8 |
Correct |
10 ms |
15180 KB |
Output is correct |
9 |
Correct |
13 ms |
15840 KB |
Output is correct |
10 |
Correct |
12 ms |
15820 KB |
Output is correct |
11 |
Correct |
11 ms |
15564 KB |
Output is correct |
12 |
Correct |
10 ms |
15564 KB |
Output is correct |
13 |
Correct |
11 ms |
15540 KB |
Output is correct |
14 |
Correct |
11 ms |
15580 KB |
Output is correct |
15 |
Correct |
10 ms |
15456 KB |
Output is correct |
16 |
Correct |
12 ms |
15592 KB |
Output is correct |
17 |
Correct |
11 ms |
15584 KB |
Output is correct |
18 |
Correct |
10 ms |
15308 KB |
Output is correct |
19 |
Correct |
14 ms |
15436 KB |
Output is correct |
20 |
Correct |
12 ms |
15464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
217 ms |
36720 KB |
Output is correct |
2 |
Correct |
91 ms |
25852 KB |
Output is correct |
3 |
Correct |
246 ms |
35476 KB |
Output is correct |
4 |
Correct |
154 ms |
29368 KB |
Output is correct |
5 |
Correct |
1057 ms |
85848 KB |
Output is correct |
6 |
Correct |
740 ms |
75384 KB |
Output is correct |
7 |
Correct |
384 ms |
63504 KB |
Output is correct |
8 |
Correct |
444 ms |
54380 KB |
Output is correct |
9 |
Correct |
466 ms |
54236 KB |
Output is correct |
10 |
Correct |
382 ms |
50304 KB |
Output is correct |
11 |
Correct |
146 ms |
34316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15180 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
9 ms |
15092 KB |
Output is correct |
4 |
Correct |
9 ms |
15180 KB |
Output is correct |
5 |
Correct |
9 ms |
15180 KB |
Output is correct |
6 |
Correct |
9 ms |
15180 KB |
Output is correct |
7 |
Correct |
10 ms |
15324 KB |
Output is correct |
8 |
Correct |
10 ms |
15180 KB |
Output is correct |
9 |
Correct |
13 ms |
15840 KB |
Output is correct |
10 |
Correct |
12 ms |
15820 KB |
Output is correct |
11 |
Correct |
11 ms |
15564 KB |
Output is correct |
12 |
Correct |
10 ms |
15564 KB |
Output is correct |
13 |
Correct |
11 ms |
15540 KB |
Output is correct |
14 |
Correct |
11 ms |
15580 KB |
Output is correct |
15 |
Correct |
10 ms |
15456 KB |
Output is correct |
16 |
Correct |
12 ms |
15592 KB |
Output is correct |
17 |
Correct |
11 ms |
15584 KB |
Output is correct |
18 |
Correct |
10 ms |
15308 KB |
Output is correct |
19 |
Correct |
14 ms |
15436 KB |
Output is correct |
20 |
Correct |
12 ms |
15464 KB |
Output is correct |
21 |
Correct |
217 ms |
36720 KB |
Output is correct |
22 |
Correct |
91 ms |
25852 KB |
Output is correct |
23 |
Correct |
246 ms |
35476 KB |
Output is correct |
24 |
Correct |
154 ms |
29368 KB |
Output is correct |
25 |
Correct |
1057 ms |
85848 KB |
Output is correct |
26 |
Correct |
740 ms |
75384 KB |
Output is correct |
27 |
Correct |
384 ms |
63504 KB |
Output is correct |
28 |
Correct |
444 ms |
54380 KB |
Output is correct |
29 |
Correct |
466 ms |
54236 KB |
Output is correct |
30 |
Correct |
382 ms |
50304 KB |
Output is correct |
31 |
Correct |
146 ms |
34316 KB |
Output is correct |
32 |
Correct |
159 ms |
33336 KB |
Output is correct |
33 |
Correct |
185 ms |
33536 KB |
Output is correct |
34 |
Correct |
417 ms |
53632 KB |
Output is correct |
35 |
Correct |
332 ms |
44516 KB |
Output is correct |
36 |
Correct |
339 ms |
49576 KB |
Output is correct |
37 |
Correct |
395 ms |
53280 KB |
Output is correct |
38 |
Correct |
380 ms |
62888 KB |
Output is correct |
39 |
Correct |
174 ms |
37740 KB |
Output is correct |
40 |
Correct |
436 ms |
55472 KB |
Output is correct |
41 |
Correct |
478 ms |
55972 KB |
Output is correct |
42 |
Correct |
519 ms |
64388 KB |
Output is correct |
43 |
Correct |
247 ms |
39368 KB |
Output is correct |
44 |
Correct |
498 ms |
47700 KB |
Output is correct |
45 |
Correct |
354 ms |
50160 KB |
Output is correct |
46 |
Correct |
299 ms |
49952 KB |
Output is correct |
47 |
Correct |
367 ms |
52652 KB |
Output is correct |
48 |
Correct |
1069 ms |
87792 KB |
Output is correct |