# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
983838 |
2024-05-16T07:12:12 Z |
vjudge1 |
Robot (JOI21_ho_t4) |
C++17 |
|
407 ms |
43204 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> graph(n + 1);
map<int, int> p[n + 1];
for(int i = 0; i < m; i ++){
int a, b, c, P;
cin >> a >> b >> c >> P;
graph[a].push_back({b, c, P});
graph[b].push_back({a, c, P});
p[a][c] += P;
p[b][c] += P;
}
vector<int> mins(n + 1, 1e18);
set<array<int, 2>> s;
s.insert({0, 1});
mins[1] = 0;
while(!s.empty()){
array<int, 2> x = *s.begin();
s.erase(s.begin());
for(auto y : graph[x[1]]){
if(mins[y[0]] > x[0] + min(y[2], p[x[1]][y[1]] - y[2])){
s.erase({mins[y[0]], y[0]});
mins[y[0]] = x[0] + min(y[2], p[x[1]][y[1]] - y[2]);
s.insert({mins[y[0]], y[0]});
}
}
}
if(mins[n] == 1e18)
cout << -1;
else
cout << mins[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
12880 KB |
Output is correct |
2 |
Correct |
22 ms |
7512 KB |
Output is correct |
3 |
Correct |
65 ms |
17440 KB |
Output is correct |
4 |
Correct |
35 ms |
10320 KB |
Output is correct |
5 |
Incorrect |
407 ms |
43204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |