Submission #1439088


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 * 5 + 1];
ll dist[70000 * 5 + 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 * 5 + b, cost};
    g[i * 5 + 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, 4, 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, 3, 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, 4, a, 4, 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, 3, b, 3, 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 * 5 + 1, inf);

    priority_queue<LP, vector<LP>, greater<LP>> q;
    dist[s * 5] = 0;
    q.push(LP(0, s * 5));
    while(!q.empty()){
        LP v = q.top();
        q.pop();

        if(v.first > dist[v.second]){
            continue;
        }

        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 * 5];
    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 720
Code Size 4491 Byte
Status WA
Exec Time 2106 ms
Memory 534996 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 190 / 190 170 / 170 360 / 360 0 / 430
Status
AC × 3
AC × 3
AC × 10
AC × 10
WA × 1
TLE × 4
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 AC 5 ms 14592 KB
sub1_in2.txt AC 5 ms 14720 KB
sub1_in3.txt AC 5 ms 14720 KB
sub2_in1.txt AC 5 ms 14592 KB
sub2_in2.txt AC 6 ms 14848 KB
sub2_in3.txt AC 11 ms 15616 KB
sub3_in1.txt AC 9 ms 15360 KB
sub3_in2.txt AC 266 ms 40948 KB
sub3_in3.txt AC 264 ms 41972 KB
sub3_in4.txt AC 317 ms 49008 KB
sub4_in1.txt TLE 2105 ms 332504 KB
sub4_in2.txt TLE 2106 ms 303064 KB
sub4_in3.txt TLE 2106 ms 534996 KB
sub4_in4.txt TLE 2106 ms 303576 KB
sub4_in5.txt WA 189 ms 54124 KB