Submission #1439093
Source Code Expand
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, int> LP;
const ll inf = 1e18;
struct E{
int to;
ll cost;
};
int h, w, n, f;
int sx, sy, gx, gy;
int a[70000];
int b[70000];
char c[70000];
int d[70000];
int e[70000];
vector<P> p[100000];
vector<P> q[100000];
vector<E> g[70000 * 3 + 1];
ll dist[70000 * 3 + 1];
void make_coord(){
rep(i, n){
p[a[i]].push_back(P(b[i], i));
q[b[i]].push_back(P(a[i], i));
}
rep(i, h){
sort(p[i].begin(), p[i].end());
}
rep(i, w){
sort(q[i].begin(), q[i].end());
}
}
void add_edge(int i, int a, int j, int b, int cost){
// cout << i << ' ' << a << ',' << j << ' ' << b << ':' << cost << endl;
E e = {j * 3 + b, cost};
g[i * 3 + a].push_back(e);
}
void add_vp(int from, int i, int v, int bs){
int s = upper_bound(p[i].begin(), p[i].end(), P(v, -1)) - p[i].begin() - 1;
if(s != -1){
add_edge(from, 0, p[i][s].second, 2, f * ll(v - p[i][s].first) + bs);
}
int t = lower_bound(p[i].begin(), p[i].end(), P(v, 0)) - p[i].begin();
if(t != p[i].size()){
add_edge(from, 0, p[i][t].second, 2, f * ll(p[i][t].first - v) + bs);
}
}
void add_vq(int from, int i, int v, int bs){
int s = upper_bound(q[i].begin(), q[i].end(), P(v, -1)) - q[i].begin() - 1;
if(s != -1){
add_edge(from, 0, q[i][s].second, 1, f * ll(v - q[i][s].first) + bs);
}
int t = lower_bound(q[i].begin(), q[i].end(), P(v, 0)) - q[i].begin();
if(t != q[i].size()){
add_edge(from, 0, q[i][t].second, 1, f * ll(q[i][t].first - v) + bs);
}
}
void make_base_edge(){
rep(i, n){
add_vq(i, b[i], a[i] - d[i], c[i] != 'N' ? e[i] : 0);
add_vp(i, a[i], b[i] + d[i], c[i] != 'E' ? e[i] : 0);
add_vq(i, b[i], a[i] + d[i], c[i] != 'S' ? e[i] : 0);
add_vp(i, a[i], b[i] - d[i], c[i] != 'W' ? e[i] : 0);
}
}
void make_pass_edge(){
rep(i, n){
for(int j = 1; j <= 4; ++j){
add_edge(i, j, i, 0, 0);
}
}
rep(i, h){
rep(j, (int)p[i].size() - 1){
int a = p[i][j].second;
int b = p[i][j + 1].second;
ll c = f * ll(p[i][j + 1].first - p[i][j].first);
add_edge(a, 2, b, 2, c);
add_edge(b, 2, a, 2, c);
}
}
rep(i, w){
rep(j, (int)q[i].size() - 1){
int a = q[i][j].second;
int b = q[i][j + 1].second;
ll c = f * ll(q[i][j + 1].first - q[i][j].first);
add_edge(a, 1, b, 1, c);
add_edge(b, 1, a, 1, c);
}
}
}
void add_goal(){
for(P& v: p[gx]){
int s = v.second;
add_edge(s, 0, n, 0, ll(f) * abs(gy - (v.first - d[s])) + (c[s] != 'W' ? e[s] : 0));
add_edge(s, 0, n, 0, ll(f) * abs(gy - (v.first + d[s])) + (c[s] != 'E' ? e[s] : 0));
}
for(P& v: q[gy]){
int s = v.second;
add_edge(s, 0, n, 0, ll(f) * abs(gx - (v.first - d[s])) + (c[s] != 'N' ? e[s] : 0));
add_edge(s, 0, n, 0, ll(f) * abs(gx - (v.first + d[s])) + (c[s] != 'S' ? e[s] : 0));
}
}
ll dijkstra(){
auto t = lower_bound(p[sx].begin(), p[sx].end(), P(sy, 0));
if(t == p[sx].end() || t->first != sy){
return -1;
}
int s = t->second;
fill_n(dist, n * 3 + 1, inf);
priority_queue<LP, vector<LP>, greater<LP>> q;
dist[s * 3] = 0;
q.push(LP(0, s * 3));
while(!q.empty()){
LP v = q.top();
q.pop();
if(v.first > dist[v.second]){
continue;
}
if(v.second == n * 3){
break;
}
for(E& e: g[v.second]){
if(dist[e.to] > v.first + e.cost){
dist[e.to] = v.first + e.cost;
q.push(LP(dist[e.to], e.to));
}
}
}
ll ans = dist[n * 3];
return ans != inf ? ans : -1;
}
int main(){
cin >> h >> w >> n >> f;
cin >> sx >> sy >> gx >> gy;
--sx;
--sy;
--gx;
--gy;
rep(i, n){
cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i];
--a[i];
--b[i];
}
make_coord();
make_base_edge();
make_pass_edge();
add_goal();
cout << dijkstra() << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Find the Route! |
User |
hipokaba |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4553 Byte |
Status |
RE |
Exec Time |
2106 ms |
Memory |
549076 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
0 / 190 |
0 / 170 |
0 / 360 |
0 / 430 |
Status |
|
|
|
AC |
× 1 |
WA |
× 8 |
TLE |
× 4 |
RE |
× 2 |
|
Set Name |
Test Cases |
Subtask1 |
sub1_in1.txt, sub1_in2.txt, sub1_in3.txt |
Subtask2 |
sub2_in1.txt, sub2_in2.txt, sub2_in3.txt |
Subtask3 |
sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt |
Subtask4 |
sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub4_in5.txt |
Case Name |
Status |
Exec Time |
Memory |
sub1_in1.txt |
WA |
4 ms |
10880 KB |
sub1_in2.txt |
WA |
5 ms |
11008 KB |
sub1_in3.txt |
WA |
5 ms |
11008 KB |
sub2_in1.txt |
AC |
4 ms |
10880 KB |
sub2_in2.txt |
WA |
5 ms |
11136 KB |
sub2_in3.txt |
WA |
8 ms |
11776 KB |
sub3_in1.txt |
WA |
8 ms |
11648 KB |
sub3_in2.txt |
WA |
202 ms |
38388 KB |
sub3_in3.txt |
WA |
238 ms |
39920 KB |
sub3_in4.txt |
RE |
555 ms |
44144 KB |
sub4_in1.txt |
TLE |
2105 ms |
549076 KB |
sub4_in2.txt |
TLE |
2106 ms |
488916 KB |
sub4_in3.txt |
TLE |
2105 ms |
295000 KB |
sub4_in4.txt |
TLE |
2106 ms |
297432 KB |
sub4_in5.txt |
RE |
232 ms |
45556 KB |