oj.uz

답안 #1007599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1007599 2024-06-25T08:54:46 Z dimashhh Soccer (JOI17_soccer) C++17
0 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int  N = 5e2 + 2, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n,m,d[N][N];
ll val[N][N];
ll a,b,c;
queue<pair<int,int>> q;
bool check(int x,int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
queue<pair<ll,pair<int,int>>> st;
int fx,fy;
ll dist[N][N];
bool vis[N][N];
void test(){
    cin >> n >> m >> a >> b >> c;
    n++;
    m++;
    int f;cin >> f;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            d[i][j] = 1e9;
            dist[i][j] = 1e17;
        }
    }
    for(int i = 1;i <= f;i++) {
        int s,t;
        cin >> s >> t;
        s++;
        t++;
        if(i == 1){
            dist[s][t] = 0;
            st.push({0,{s,t}});
        }
        d[s][t] = 0;
        q.push({s,t});
        fx = s;fy = t;
    }
    while(!q.empty()){
        auto [x,y] = q.front();q.pop();
        val[x][y] = d[x][y] * c;
        for(int i = 0;i < 4;i++){
            int x1 = x + dx[i],y1 = y + dy[i];
            if(check(x1,y1) && d[x1][y1] > d[x][y] + 1){
                d[x1][y1] = d[x][y] +1;
                q.push({x1,y1});
            }
        }
    }
    while(!st.empty()){
        auto [d,t] = (st.front());
        st.pop();
        int x = t.first,y = t.second;
        // if(vis[x][y]) continue;
        // cout << x << ' ' << y << ' ' << dist[x][y] << '\n';
        vis[x][y] = 1;
        for(int x1 = 1;x1 <= n;x1++) {
            ll dd = min(abs(x - x1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x1][y] + abs(x1 - x) * a + (x1 != x ? b : 0));
            if (dd < dist[x1][y]) {
                dist[x1][y] = dd;
                st.push({dist[x1][y], {x1, y}});
            }
        }
        for(int y1 = m;y1 >= 1;y1--) {
            ll dd = min(abs(y - y1) * 1ll * c + dist[x][y],
                        dist[x][y] + val[x][y1] + abs(y - y1) * a + (y1 != y ? b : 0));
            if (dd < dist[x][y1]) {
                dist[x][y1] = dd;
                st.push({dist[x][y1], {x, y1}});
            }
        }
    }
    cout << dist[fx][fy];
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1327 ms 25352 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Runtime error 509 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3053 ms 40028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1327 ms 25352 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Runtime error 509 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -