# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
858526 |
2023-10-08T15:42:54 Z |
damwuan |
Robot (JOI21_ho_t4) |
C++17 |
|
147 ms |
30152 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<int> vi;
const ll maxn=2e5+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,m;
struct Edge
{
int v,c,p;
};
vector<Edge> adj[maxn];
priority_queue<pii,vii,greater<pii>> pq;
int sum[maxn],mn[maxn],dp[maxn];
void sol()
{
cin >> n>>m;
for1(i,1,m)
{
int u,v,c,p;cin >> u>> v>>c>>p;
adj[u].pb({v,c,p});
adj[v].pb({u,c,p});
}
for1(i,1,n) dp[i]=inf;
pq.push({0,1});
dp[1]=0;
while (!pq.empty())
{
int x=pq.top().fi;
int u=pq.top().se;
pq.pop();
if (dp[u]!=x) continue;
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
sum[c]=0;
mn[c]=inf;
}
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
sum[c]+=p;
mn[c]=min(mn[c],dp[v]);//mn[c] la min dp[v1]
}
for(Edge x:adj[u])
{
int v=x.v;
int c=x.c;
int p=x.p;
if (dp[v]>dp[u]+min(p,sum[c]-p))
{
dp[v]=dp[u]+min(p,sum[c]-p);
pq.push({dp[v],v});
}
if (dp[v]>mn[c]+sum[c]-p)
{
dp[v]=mn[c]+sum[c]-p;
pq.push({dp[v],v});
}
}
}
if (dp[n]>=inf) cout <<"-1";
else cout << dp[n];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
3 5 2 4 1
*/
Compilation message
Main.cpp: In function 'void sol()':
Main.cpp:55:17: warning: unused variable 'v' [-Wunused-variable]
55 | int v=x.v;
| ^
Main.cpp:57:17: warning: unused variable 'p' [-Wunused-variable]
57 | int p=x.p;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9816 KB |
Output is correct |
5 |
Correct |
2 ms |
9664 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
3 ms |
9736 KB |
Output is correct |
9 |
Correct |
2 ms |
9816 KB |
Output is correct |
10 |
Correct |
3 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
3 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9676 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9784 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
3 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
19 |
Correct |
3 ms |
9820 KB |
Output is correct |
20 |
Correct |
3 ms |
9820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
17492 KB |
Output is correct |
2 |
Correct |
17 ms |
13312 KB |
Output is correct |
3 |
Correct |
48 ms |
23104 KB |
Output is correct |
4 |
Correct |
28 ms |
14956 KB |
Output is correct |
5 |
Correct |
109 ms |
28040 KB |
Output is correct |
6 |
Correct |
92 ms |
28940 KB |
Output is correct |
7 |
Correct |
91 ms |
28168 KB |
Output is correct |
8 |
Correct |
94 ms |
27652 KB |
Output is correct |
9 |
Correct |
97 ms |
27728 KB |
Output is correct |
10 |
Correct |
53 ms |
21536 KB |
Output is correct |
11 |
Correct |
39 ms |
18000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9564 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
2 ms |
9816 KB |
Output is correct |
5 |
Correct |
2 ms |
9664 KB |
Output is correct |
6 |
Correct |
2 ms |
9564 KB |
Output is correct |
7 |
Correct |
2 ms |
9564 KB |
Output is correct |
8 |
Correct |
3 ms |
9736 KB |
Output is correct |
9 |
Correct |
2 ms |
9816 KB |
Output is correct |
10 |
Correct |
3 ms |
9816 KB |
Output is correct |
11 |
Correct |
3 ms |
9816 KB |
Output is correct |
12 |
Correct |
3 ms |
9820 KB |
Output is correct |
13 |
Correct |
3 ms |
9676 KB |
Output is correct |
14 |
Correct |
2 ms |
9820 KB |
Output is correct |
15 |
Correct |
2 ms |
9784 KB |
Output is correct |
16 |
Correct |
3 ms |
9820 KB |
Output is correct |
17 |
Correct |
3 ms |
9820 KB |
Output is correct |
18 |
Correct |
2 ms |
9564 KB |
Output is correct |
19 |
Correct |
3 ms |
9820 KB |
Output is correct |
20 |
Correct |
3 ms |
9820 KB |
Output is correct |
21 |
Correct |
36 ms |
17492 KB |
Output is correct |
22 |
Correct |
17 ms |
13312 KB |
Output is correct |
23 |
Correct |
48 ms |
23104 KB |
Output is correct |
24 |
Correct |
28 ms |
14956 KB |
Output is correct |
25 |
Correct |
109 ms |
28040 KB |
Output is correct |
26 |
Correct |
92 ms |
28940 KB |
Output is correct |
27 |
Correct |
91 ms |
28168 KB |
Output is correct |
28 |
Correct |
94 ms |
27652 KB |
Output is correct |
29 |
Correct |
97 ms |
27728 KB |
Output is correct |
30 |
Correct |
53 ms |
21536 KB |
Output is correct |
31 |
Correct |
39 ms |
18000 KB |
Output is correct |
32 |
Correct |
53 ms |
23336 KB |
Output is correct |
33 |
Correct |
66 ms |
19400 KB |
Output is correct |
34 |
Correct |
82 ms |
24276 KB |
Output is correct |
35 |
Correct |
60 ms |
21972 KB |
Output is correct |
36 |
Correct |
82 ms |
21364 KB |
Output is correct |
37 |
Correct |
80 ms |
25220 KB |
Output is correct |
38 |
Correct |
84 ms |
27824 KB |
Output is correct |
39 |
Correct |
69 ms |
25424 KB |
Output is correct |
40 |
Correct |
135 ms |
28820 KB |
Output is correct |
41 |
Correct |
147 ms |
29336 KB |
Output is correct |
42 |
Correct |
103 ms |
27592 KB |
Output is correct |
43 |
Correct |
45 ms |
19928 KB |
Output is correct |
44 |
Correct |
75 ms |
30152 KB |
Output is correct |
45 |
Correct |
94 ms |
23844 KB |
Output is correct |
46 |
Correct |
66 ms |
23272 KB |
Output is correct |
47 |
Correct |
94 ms |
24756 KB |
Output is correct |
48 |
Correct |
116 ms |
29432 KB |
Output is correct |