| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 631918 |
2022-08-19T07:11:18 Z |
minhcool |
버스 (JOI14_bus) |
C++17 |
|
117 ms |
192860 KB |
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, ii> iiii;
const int N = 1e3 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int w, h, n, stx, sty, enx, eny;
map<int, ii> options[N][N];// from (x, y) to one of four directions
int x[] = {0, 1, 0, -1};
int y[] = {1, 0, -1, 0};
bool vis[N][N];
map<int, int> mn_dist[N][N];
void dijik(){
priority_queue<iiii, vector<iiii>, greater<iiii>> pq;
/*
for(int i = 1; i <= w; i++){
for(int j = 1; j <= h; j++) mn_dist[i][j] = oo;
}*/
vector<int> b;
for(auto it : mn_dist[stx][sty]) b.pb(it.fi);
for(auto it : b){
mn_dist[stx][sty][it] = 0;
pq.push({{0, it}, {stx, sty}});
}
while(!pq.empty()){
int d = pq.top().fi.fi, curbus = pq.top().fi.se, curx = pq.top().se.fi, cury = pq.top().se.se;
pq.pop();
if(d != mn_dist[curx][cury][curbus]) continue;
if(!vis[curx][cury]){
vis[curx][cury] = 1;
b.clear();
for(auto it : mn_dist[curx][cury]) b.pb(it.fi);
for(auto it : b){
//cout << stx << " " << sty << " " << it << " " << mn_dist[stx][sty][it] << "\n";
if(mn_dist[curx][cury][it] > d + 1){
mn_dist[curx][cury][it] = d + 1;
pq.push({{mn_dist[curx][cury][it], it}, {curx, cury}});
}
}
}
ii temp = options[curx][cury][curbus];
//cout << d << " " << curbus << " " << curx << " " << cury << "\n";
for(int i = 0; i < 4; i++){
int nxtx = curx + x[i], nxty = cury + y[i];
if(mn_dist[nxtx][nxty].find(curbus) == mn_dist[nxtx][nxty].end()) continue;
int mini = oo;
int nxt = d - (d % temp.fi) + temp.se;
if(nxt < d) nxt += temp.fi;
mini = min(mini, nxt);
mini++;
if(mini < mn_dist[nxtx][nxty][curbus]){
mn_dist[nxtx][nxty][curbus] = mini;
pq.push({{mn_dist[nxtx][nxty][curbus], curbus}, {nxtx, nxty}});
}
}
}
}
void process(){
cin >> h >> w >> sty >> stx >> eny >> enx;
cin >> n;
for(int i = 1; i <= n; i++){
int x1, y1, x2, y2, t;
cin >> x1 >> y1 >> x2 >> y2 >> t;
swap(x1, y1), swap(x2, y2);
int cnt = 0, itrx = x1, itry = y1, cur = 0;
int peri = (x2 - x1 + y2 - y1) * 2;
for(int j = 0; j < peri; j++){
mn_dist[itrx][itry][i] = oo;
int nxtx = itrx + x[cur], nxty = itry + y[cur];
//cout << i << " " << j << " " << itrx << " " << itry << "\n";
if(nxtx < x1 || nxtx > x2 || nxty < y1 || nxty > y2) cur++;
assert(cur <= 3);
nxtx = itrx + x[cur], nxty = itry + y[cur];
int fi_trip;
if(j < t) fi_trip = peri - (t - j);
else fi_trip = j - t;
options[itrx][itry][i] = {peri, fi_trip};
itrx += x[cur], itry += y[cur];
}
}
//return;
dijik();
int ans = oo;
for(auto it : mn_dist[enx][eny]) ans = min(ans, it.se);
cout << ans;
//cout << mn_dist[enx][eny];
}
signed main(){
ios_base::sync_with_stdio(0);
int t = 1;
//cin >> t;
while(t--) process();
}
Compilation message
bus.cpp: In function 'void process()':
bus.cpp:83:13: warning: unused variable 'cnt' [-Wunused-variable]
83 | int cnt = 0, itrx = x1, itry = y1, cur = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
192732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
113 ms |
192732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
192788 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
192860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
