# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
685088 |
2023-01-23T10:16:26 Z |
saayan007 |
Robot (JOI21_ho_t4) |
C++14 |
|
3000 ms |
21992 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
struct DEdge {
ll to, col, wt;
DEdge(ll to, ll col, ll wt) : to(to), col(col), wt(wt) {}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll n, m;
cin >> n >> m;
vector<DEdge> adj[n + 1];
fur(i, 1, m) {
ll a, b, c, p;
cin >> a >> b >> c >> p;
adj[a].pb(b, c, p);
adj[b].pb(a, c, p);
}
bool proc[n + 1] = {};
ll dist[n + 1];
fur(i, 0, n) {
dist[i] = -1;
}
priority_queue<pl> q;
dist[1] = 0;
// q.emplace(-dist[1], 1);
q.push(mp(-dist[1], 1));
while(!q.empty()) {
ll a = q.top().sc;
q.pop();
if(proc[a])
continue;
proc[a] = 1;
ll cost[m + 1] = {};
for(auto [b, c, p] : adj[a]) {
cost[c] += p;
}
ll min_cost = cost[1];
fur(i, 1, m) {
min_cost = min(min_cost, cost[i]);
}
for(auto [b, c, p] : adj[a]) {
if(proc[b])
continue;
ll wt = 0;
if(cost[c] > p) {
wt = min_cost + p;
}
if(dist[b] == -1 || dist[b] > dist[a] + wt) {
dist[b] = dist[a] + wt;
// q.emplace(-dist[b], b);
q.push(mp(-dist[b], b));
}
}
}
cout << dist[n] << nl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:63:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
63 | for(auto [b, c, p] : adj[a]) {
| ^
Main.cpp:72:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto [b, c, p] : adj[a]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2469 ms |
9432 KB |
Output is correct |
2 |
Correct |
659 ms |
4568 KB |
Output is correct |
3 |
Correct |
2724 ms |
15312 KB |
Output is correct |
4 |
Correct |
1551 ms |
6788 KB |
Output is correct |
5 |
Execution timed out |
3058 ms |
21992 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |