# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
836778 |
2023-08-24T15:37:49 Z |
TS_2392 |
Robot (JOI21_ho_t4) |
C++17 |
|
1008 ms |
114844 KB |
#include <bits/stdc++.h>
using namespace std;
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}
#define epl emplace
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 1e5 + 3;
const ll oo = 1e17;
int n, m;
struct adjNode{
pii v;
int c, p;
};
map< int, ll > sump[N], d[N];
map< int, vector<adjNode> > adj[N];
priority_queue< pair<ll, pii>, vector< pair<ll, pii> >, greater< pair<ll, pii> > > pq;
void add_edge(pii a, pii b, int c, int p){
adj[a.fi][a.se].pb({b, c, p});
adj[b.fi][b.se].pb({a, c, p});
}
int main(){
SPEED; fileIO("text");
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int u, v, c, p;
cin >> u >> v >> c >> p;
add_edge({u, 0}, {v, 0}, c, p);
add_edge({u, 0}, {v, c}, c, p);
add_edge({u, c}, {v, 0}, c, p);
}
for(int u = 1; u <= n; ++u){
//dbg(u); EL;
for(auto &[c, x] : adj[u]){
ll tot = 0;
for(auto e : x) tot += e.p;
d[u][c] = oo; sump[u][c] = tot;
//dbg(c); dbg(sump[u][c]); EL;
}
}
d[1][0] = 0; pq.epl(0, mp(1, 0));
while(!pq.empty()){
ll dist = pq.top().fi;
int u, x; tie(u, x) = pq.top().se;
pq.pop();
if(dist != d[u][x]) continue;
for(auto &[b, c, p] : adj[u][x]){
int v, y; tie(v, y) = b;
if(x == 0){
if(!y && minimize(d[v][y], d[u][x] + min(1LL * p, sump[u][c] - p))) pq.epl(d[v][y], mp(v, y));
else if(y && minimize(d[v][y], d[u][x])) pq.epl(d[v][y], mp(v, y));
}
else if(!y && minimize(d[v][y], d[u][x] + sump[u][x] - p)) pq.epl(d[v][y], mp(v, y));
}
}
cout << (d[n][0] == oo ? -1 : d[n][0]);
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:5:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:12: note: in expansion of macro 'fileIO'
40 | SPEED; fileIO("text");
| ^~~~~~
Main.cpp:5:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:40:12: note: in expansion of macro 'fileIO'
40 | SPEED; fileIO("text");
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14408 KB |
Output is correct |
2 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
45632 KB |
Output is correct |
2 |
Correct |
80 ms |
30432 KB |
Output is correct |
3 |
Correct |
196 ms |
45032 KB |
Output is correct |
4 |
Correct |
112 ms |
36568 KB |
Output is correct |
5 |
Correct |
1008 ms |
114844 KB |
Output is correct |
6 |
Correct |
814 ms |
104048 KB |
Output is correct |
7 |
Correct |
371 ms |
84988 KB |
Output is correct |
8 |
Correct |
474 ms |
83908 KB |
Output is correct |
9 |
Correct |
487 ms |
83860 KB |
Output is correct |
10 |
Correct |
326 ms |
68740 KB |
Output is correct |
11 |
Incorrect |
149 ms |
58848 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14408 KB |
Output is correct |
2 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |