# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
710820 |
2023-03-15T21:05:38 Z |
blacktulip |
Robot (JOI21_ho_t4) |
C++17 |
|
761 ms |
78888 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
int n,m,a[li],k,flag,t,x;
lo cev,cost[li],mn1[li],mn2[li];
vector<pair<int,pair<int,int>>> v[li];
unordered_map<int,long long> mpp[li];
//~ unordered_map<int,bool> vis[li];
bool vis[li][4];
inline int in(){
int x;
scanf("%lld",&x);
return x;
}
inline void sp(){
priority_queue<pair<lo,pair<int,int>>> pq;
pq.push({0,{0,1}});
for(int i=1;i<=max(n,m);i++){
cost[i]=20000000000000001;
mn1[i]=20000000000000001;
mn2[i]=20000000000000001;
}
cev=20000000000000001;
while(pq.size()){
lo co=-pq.top().fi;
int yes=pq.top().se.fi;
int node=pq.top().se.se;
pq.pop();
if(vis[node][yes])continue;
vis[node][yes]=1;
//~ cout<<node<<" :: "<<co<<endl;
//~ cout<<co<<endl;
cost[node]=min(cost[node],co);
if(node==n){cev=min(cev,co);continue;}
for(auto go:v[node]){
if(vis[go.fi][0]==0)pq.push({-co-mpp[node][go.se.fi]+go.se.se,{0,go.fi}});
if(vis[go.fi][0]==0)pq.push({-co-go.se.se,{0,go.fi}});
mn1[go.se.fi]=min(mn1[go.se.fi],cost[go.fi]);
//~ if(mn2[go.se.fi]<mn1[go.se.fi])swap(mn2[go.se.fi],mn1[go.se.fi]);
}
for(auto go:v[node]){
if(cost[go.fi]>mn1[go.se.fi]+mpp[node][go.se.fi]-go.se.se){
//~ cost[go.fi]=mn1[go.se.fi]+mpp[node][go.se.fi]-go.se.se;
//~ vis[go.fi]=0;
//~ cout<<go.fi<<" :: "<<cost[go.fi]<<" :: "<<node<<" :: "<<go.se.se<<" :: "<<mn1[go.se.fi]<<" :: "<<go.se.fi<<endl;
pq.push({-(mn1[go.se.fi]+mpp[node][go.se.fi]-go.se.se),{1,go.fi}});
}
}
for(auto go:v[node]){
mn1[go.se.fi]=20000000000000001;
mn2[go.se.fi]=20000000000000001;
}
}
if(cev>=20000000000000001)cev=-1;
printf("%lld\n",cev);
}
int32_t main(void){
n=in(),m=in();
for(int i=1;i<=m;i++){
int x=in(),y=in(),c=in(),p=in();
v[x].pb({y,{c,p}});
v[y].pb({x,{c,p}});
mpp[x][c]+=p;
mpp[y][c]+=p;
}
sp();
return 0;
}
Compilation message
Main.cpp: In function 'long long int in()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%lld",&x);
| ~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
2 |
Correct |
9 ms |
15976 KB |
Output is correct |
3 |
Correct |
9 ms |
15956 KB |
Output is correct |
4 |
Correct |
8 ms |
15956 KB |
Output is correct |
5 |
Correct |
8 ms |
15956 KB |
Output is correct |
6 |
Correct |
10 ms |
15968 KB |
Output is correct |
7 |
Correct |
9 ms |
16084 KB |
Output is correct |
8 |
Correct |
10 ms |
16140 KB |
Output is correct |
9 |
Correct |
16 ms |
16596 KB |
Output is correct |
10 |
Correct |
12 ms |
16596 KB |
Output is correct |
11 |
Correct |
11 ms |
16596 KB |
Output is correct |
12 |
Correct |
15 ms |
16532 KB |
Output is correct |
13 |
Correct |
13 ms |
16788 KB |
Output is correct |
14 |
Correct |
12 ms |
16788 KB |
Output is correct |
15 |
Correct |
10 ms |
16212 KB |
Output is correct |
16 |
Correct |
11 ms |
16408 KB |
Output is correct |
17 |
Correct |
11 ms |
16384 KB |
Output is correct |
18 |
Correct |
9 ms |
16084 KB |
Output is correct |
19 |
Correct |
11 ms |
16596 KB |
Output is correct |
20 |
Correct |
11 ms |
16212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
191 ms |
34620 KB |
Output is correct |
2 |
Correct |
85 ms |
25236 KB |
Output is correct |
3 |
Correct |
229 ms |
45720 KB |
Output is correct |
4 |
Correct |
126 ms |
31200 KB |
Output is correct |
5 |
Correct |
583 ms |
77788 KB |
Output is correct |
6 |
Correct |
615 ms |
78888 KB |
Output is correct |
7 |
Correct |
425 ms |
71512 KB |
Output is correct |
8 |
Correct |
447 ms |
50128 KB |
Output is correct |
9 |
Correct |
477 ms |
50252 KB |
Output is correct |
10 |
Correct |
294 ms |
43040 KB |
Output is correct |
11 |
Correct |
120 ms |
35684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15956 KB |
Output is correct |
2 |
Correct |
9 ms |
15976 KB |
Output is correct |
3 |
Correct |
9 ms |
15956 KB |
Output is correct |
4 |
Correct |
8 ms |
15956 KB |
Output is correct |
5 |
Correct |
8 ms |
15956 KB |
Output is correct |
6 |
Correct |
10 ms |
15968 KB |
Output is correct |
7 |
Correct |
9 ms |
16084 KB |
Output is correct |
8 |
Correct |
10 ms |
16140 KB |
Output is correct |
9 |
Correct |
16 ms |
16596 KB |
Output is correct |
10 |
Correct |
12 ms |
16596 KB |
Output is correct |
11 |
Correct |
11 ms |
16596 KB |
Output is correct |
12 |
Correct |
15 ms |
16532 KB |
Output is correct |
13 |
Correct |
13 ms |
16788 KB |
Output is correct |
14 |
Correct |
12 ms |
16788 KB |
Output is correct |
15 |
Correct |
10 ms |
16212 KB |
Output is correct |
16 |
Correct |
11 ms |
16408 KB |
Output is correct |
17 |
Correct |
11 ms |
16384 KB |
Output is correct |
18 |
Correct |
9 ms |
16084 KB |
Output is correct |
19 |
Correct |
11 ms |
16596 KB |
Output is correct |
20 |
Correct |
11 ms |
16212 KB |
Output is correct |
21 |
Correct |
191 ms |
34620 KB |
Output is correct |
22 |
Correct |
85 ms |
25236 KB |
Output is correct |
23 |
Correct |
229 ms |
45720 KB |
Output is correct |
24 |
Correct |
126 ms |
31200 KB |
Output is correct |
25 |
Correct |
583 ms |
77788 KB |
Output is correct |
26 |
Correct |
615 ms |
78888 KB |
Output is correct |
27 |
Correct |
425 ms |
71512 KB |
Output is correct |
28 |
Correct |
447 ms |
50128 KB |
Output is correct |
29 |
Correct |
477 ms |
50252 KB |
Output is correct |
30 |
Correct |
294 ms |
43040 KB |
Output is correct |
31 |
Correct |
120 ms |
35684 KB |
Output is correct |
32 |
Correct |
232 ms |
43600 KB |
Output is correct |
33 |
Correct |
222 ms |
43920 KB |
Output is correct |
34 |
Correct |
344 ms |
50480 KB |
Output is correct |
35 |
Correct |
291 ms |
47180 KB |
Output is correct |
36 |
Correct |
362 ms |
54668 KB |
Output is correct |
37 |
Correct |
460 ms |
61184 KB |
Output is correct |
38 |
Correct |
546 ms |
72568 KB |
Output is correct |
39 |
Correct |
286 ms |
49612 KB |
Output is correct |
40 |
Correct |
510 ms |
50912 KB |
Output is correct |
41 |
Correct |
565 ms |
51160 KB |
Output is correct |
42 |
Correct |
539 ms |
60456 KB |
Output is correct |
43 |
Correct |
187 ms |
37328 KB |
Output is correct |
44 |
Correct |
485 ms |
53304 KB |
Output is correct |
45 |
Correct |
400 ms |
45172 KB |
Output is correct |
46 |
Correct |
374 ms |
45240 KB |
Output is correct |
47 |
Correct |
388 ms |
56484 KB |
Output is correct |
48 |
Correct |
761 ms |
78480 KB |
Output is correct |