# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
444592 |
2021-07-14T10:08:31 Z |
O_o |
Robot (JOI21_ho_t4) |
C++14 |
|
1185 ms |
88904 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";
const int logN = 20;
const int M = 1000000007;
const int INF = 1e17;
#define PI 3.14159265;
const int N = 200005;
#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>
#define PQ priority_queue<int>
void setIO(string d_name = "") {
ios_base::sync_with_stdio(0); cin.tie(0);
if(sz(d_name)){
freopen((d_name+".in").c_str(), "r", stdin);
freopen((d_name+".out").c_str(), "w", stdout);
}
}
map<int, vector<pair<int, Pii>>> adj[100001];
map<int, int> grp[100001];
int32_t main()
{
setIO();
int n, m;
cin>>n>>m;
rep(_,0,m)
{
int a, b, c, p;
cin>>a>>b>>c>>p;
adj[a][c].pb(mp(b, mp(c, p)));
adj[b][c].pb(mp(a, mp(c, p)));
grp[a][c]+= p;
grp[b][c]+= p;
}
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
Vi dist(100001, INF);
map<int, int> dp[100001];
dist[1]= 0;
pq.push({0, 1, 0});
while(!pq.empty())
{
int x, c, p;
tie(p, x, c)= pq.top();
pq.pop();
if(c)
{
if(p != dp[x][c])
{
continue;
}
for(auto e: adj[x][c])
{
int cost= p+grp[x][c];
if(cost-e.se.se < dist[e.fi])
{
dist[e.fi]= cost-e.se.se;
pq.push({dist[e.fi], e.fi, 0});
}
}
}
else
{
if(p != dist[x])
{
continue;
}
for(auto e1: adj[x])
{
for(auto e2: e1.se)
{
if(dist[e2.fi] > p + e2.se.se)
{
dist[e2.fi]= p+e2.se.se;
pq.push({dist[e2.fi], e2.fi, 0});
}
if(dist[e2.fi] > p + grp[x][e2.se.fi] - e2.se.se)
{
dist[e2.fi]= p + grp[x][e2.se.fi] - e2.se.se;
pq.push({dist[e2.fi], e2.fi, 0});
}
if(!dp[e2.fi].count(e2.se.fi) || dp[e2.fi][e2.se.fi] > p)
{
dp[e2.fi][e2.se.fi]= p;
pq.push({dp[e2.fi][e2.se.fi], e2.fi, e2.se.fi});
}
}
}
}
}
if(dist[n] == INF)
{
cout<<"-1";
}
else
{
cout<<dist[n];
}
return 0;
}
Compilation message
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((d_name+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((d_name+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15180 KB |
Output is correct |
2 |
Correct |
9 ms |
15164 KB |
Output is correct |
3 |
Correct |
9 ms |
15180 KB |
Output is correct |
4 |
Correct |
9 ms |
15180 KB |
Output is correct |
5 |
Correct |
9 ms |
15236 KB |
Output is correct |
6 |
Correct |
9 ms |
15164 KB |
Output is correct |
7 |
Correct |
10 ms |
15308 KB |
Output is correct |
8 |
Correct |
10 ms |
15180 KB |
Output is correct |
9 |
Correct |
13 ms |
15816 KB |
Output is correct |
10 |
Correct |
13 ms |
15692 KB |
Output is correct |
11 |
Correct |
11 ms |
15564 KB |
Output is correct |
12 |
Correct |
11 ms |
15560 KB |
Output is correct |
13 |
Correct |
11 ms |
15564 KB |
Output is correct |
14 |
Correct |
12 ms |
15552 KB |
Output is correct |
15 |
Correct |
11 ms |
15384 KB |
Output is correct |
16 |
Correct |
12 ms |
15560 KB |
Output is correct |
17 |
Correct |
11 ms |
15504 KB |
Output is correct |
18 |
Correct |
10 ms |
15308 KB |
Output is correct |
19 |
Correct |
11 ms |
15444 KB |
Output is correct |
20 |
Correct |
11 ms |
15436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
36524 KB |
Output is correct |
2 |
Correct |
106 ms |
25788 KB |
Output is correct |
3 |
Correct |
276 ms |
35196 KB |
Output is correct |
4 |
Correct |
149 ms |
29304 KB |
Output is correct |
5 |
Correct |
1132 ms |
86840 KB |
Output is correct |
6 |
Correct |
906 ms |
76612 KB |
Output is correct |
7 |
Correct |
366 ms |
59032 KB |
Output is correct |
8 |
Correct |
504 ms |
54244 KB |
Output is correct |
9 |
Correct |
502 ms |
54188 KB |
Output is correct |
10 |
Correct |
383 ms |
50044 KB |
Output is correct |
11 |
Correct |
148 ms |
34384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15180 KB |
Output is correct |
2 |
Correct |
9 ms |
15164 KB |
Output is correct |
3 |
Correct |
9 ms |
15180 KB |
Output is correct |
4 |
Correct |
9 ms |
15180 KB |
Output is correct |
5 |
Correct |
9 ms |
15236 KB |
Output is correct |
6 |
Correct |
9 ms |
15164 KB |
Output is correct |
7 |
Correct |
10 ms |
15308 KB |
Output is correct |
8 |
Correct |
10 ms |
15180 KB |
Output is correct |
9 |
Correct |
13 ms |
15816 KB |
Output is correct |
10 |
Correct |
13 ms |
15692 KB |
Output is correct |
11 |
Correct |
11 ms |
15564 KB |
Output is correct |
12 |
Correct |
11 ms |
15560 KB |
Output is correct |
13 |
Correct |
11 ms |
15564 KB |
Output is correct |
14 |
Correct |
12 ms |
15552 KB |
Output is correct |
15 |
Correct |
11 ms |
15384 KB |
Output is correct |
16 |
Correct |
12 ms |
15560 KB |
Output is correct |
17 |
Correct |
11 ms |
15504 KB |
Output is correct |
18 |
Correct |
10 ms |
15308 KB |
Output is correct |
19 |
Correct |
11 ms |
15444 KB |
Output is correct |
20 |
Correct |
11 ms |
15436 KB |
Output is correct |
21 |
Correct |
249 ms |
36524 KB |
Output is correct |
22 |
Correct |
106 ms |
25788 KB |
Output is correct |
23 |
Correct |
276 ms |
35196 KB |
Output is correct |
24 |
Correct |
149 ms |
29304 KB |
Output is correct |
25 |
Correct |
1132 ms |
86840 KB |
Output is correct |
26 |
Correct |
906 ms |
76612 KB |
Output is correct |
27 |
Correct |
366 ms |
59032 KB |
Output is correct |
28 |
Correct |
504 ms |
54244 KB |
Output is correct |
29 |
Correct |
502 ms |
54188 KB |
Output is correct |
30 |
Correct |
383 ms |
50044 KB |
Output is correct |
31 |
Correct |
148 ms |
34384 KB |
Output is correct |
32 |
Correct |
161 ms |
33316 KB |
Output is correct |
33 |
Correct |
202 ms |
33508 KB |
Output is correct |
34 |
Correct |
527 ms |
53424 KB |
Output is correct |
35 |
Correct |
372 ms |
44276 KB |
Output is correct |
36 |
Correct |
392 ms |
49180 KB |
Output is correct |
37 |
Correct |
402 ms |
53528 KB |
Output is correct |
38 |
Correct |
410 ms |
65160 KB |
Output is correct |
39 |
Correct |
170 ms |
37796 KB |
Output is correct |
40 |
Correct |
495 ms |
55620 KB |
Output is correct |
41 |
Correct |
544 ms |
55836 KB |
Output is correct |
42 |
Correct |
583 ms |
64128 KB |
Output is correct |
43 |
Correct |
251 ms |
39184 KB |
Output is correct |
44 |
Correct |
510 ms |
47820 KB |
Output is correct |
45 |
Correct |
366 ms |
50068 KB |
Output is correct |
46 |
Correct |
315 ms |
49912 KB |
Output is correct |
47 |
Correct |
344 ms |
52640 KB |
Output is correct |
48 |
Correct |
1185 ms |
88904 KB |
Output is correct |