제출 #1195829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195829		niepamietamhasla	Soccer (JOI17_soccer)	C++20	0 / 100	815 ms	327680 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m, A, B, C;
int k;
short x, y;

struct d{
    short a;
    short b;
    ll koszt;
};

const int MAXN = 505;

queue<d> q;
ll odl[MAXN][MAXN][2];

struct e{
    short a;
    short b;
    short kt;
    ll koszt;
};

short odl2[MAXN][MAXN];

void bfs(){
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            odl2[i][j] = -1;
        }
    }
    while(!q.empty()){
        auto e = q.front();
        q.pop();
        if(odl2[e.a][e.b] != -1) continue;
        odl2[e.a][e.b] = e.koszt;
        if(e.a > 0 and odl2[e.a-1][e.b] == -1){
            q.push({e.a - 1, e.b, e.koszt + 1});
        }
        if(e.a < n and odl2[e.a+1][e.b] == -1){
            q.push({e.a + 1, e.b, e.koszt + 1});

        }
        if(e.b > 0 and odl2[e.a][e.b-1] == -1){
            q.push({e.a, e.b - 1, e.koszt + 1});
        }
        if(e.b < m and odl2[e.a][e.b+1] == -1){
            q.push({e.a, e.b + 1, e.koszt + 1});
        }
    }
    return;
}

struct comp{
    bool operator()(const e &e1, const e &e2) const {
        if(e1.koszt != e2.koszt) return e1.koszt > e2.koszt;
        return false;
    }
};

priority_queue<e, vector<e>, comp> pq;

void dijkstra(pair<int,int> st){
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= m; ++j){
            odl[i][j][0] = -1;
            odl[i][j][1] = -1;
        }
    }
    pq.push({st.first, st.second, 0, 0});
    pq.push({st.first, st.second, 1, 0});
    while(!pq.empty()){
        auto u = pq.top();
        pq.pop();
        if(odl[u.a][u.b][u.kt] != -1) continue;
        odl[u.a][u.b][u.kt] = u.koszt;
        //cout << u.a << " " << u.b << " " << u.kt << " " << u.koszt << " u\n";
        for(int l = 0; l <= n; ++l){
            if(l == u.a) continue;
            if(u.kt == 0){
            	if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + u.koszt});
            	if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, B + A * abs(l - u.a) + u.koszt});	
            }
            else{
            	if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + C * odl2[u.a][u.b] + u.koszt});
            	if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.a) + u.koszt});	
            }
        }
        for(int l = 0; l <= m; ++l){
            if(l == u.b) continue;
            if(u.kt == 0){
            	if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + u.koszt});
            	if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, B + A * abs(l - u.b) + u.koszt});	
            }
            else{
            	if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + C * odl2[u.a][u.b] + u.koszt});
            	if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.b) + u.koszt});	
            }
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> k;
    pair<short,short> start;
    pair<short,short> koniec;
    for(int i = 0; i < k; ++i){
        cin >> x >> y;
        if(i == 0) start = {x,y};
        if(i == k-1) koniec = {x,y};
        q.push({x, y, 0});
    }
    bfs();
    dijkstra(start);
    cout << min(odl[koniec.first][koniec.second][0], odl[koniec.first][koniec.second][1]) << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp: In function 'void bfs()':
soccer.cpp:41:25: warning: narrowing conversion of '(((int)e.d::a) - 1)' from 'int' to 'short int' [-Wnarrowing]
   41 |             q.push({e.a - 1, e.b, e.koszt + 1});
      |                     ~~~~^~~
soccer.cpp:44:25: warning: narrowing conversion of '(((int)e.d::a) + 1)' from 'int' to 'short int' [-Wnarrowing]
   44 |             q.push({e.a + 1, e.b, e.koszt + 1});
      |                     ~~~~^~~
soccer.cpp:48:30: warning: narrowing conversion of '(((int)e.d::b) - 1)' from 'int' to 'short int' [-Wnarrowing]
   48 |             q.push({e.a, e.b - 1, e.koszt + 1});
      |                          ~~~~^~~
soccer.cpp:51:30: warning: narrowing conversion of '(((int)e.d::b) + 1)' from 'int' to 'short int' [-Wnarrowing]
   51 |             q.push({e.a, e.b + 1, e.koszt + 1});
      |                          ~~~~^~~
soccer.cpp: In function 'void dijkstra(std::pair<int, int>)':
soccer.cpp:73:17: warning: narrowing conversion of 'st.std::pair<int, int>::first' from 'int' to 'short int' [-Wnarrowing]
   73 |     pq.push({st.first, st.second, 0, 0});
      |              ~~~^~~~~
soccer.cpp:73:27: warning: narrowing conversion of 'st.std::pair<int, int>::second' from 'int' to 'short int' [-Wnarrowing]
   73 |     pq.push({st.first, st.second, 0, 0});
      |                        ~~~^~~~~~
soccer.cpp:74:17: warning: narrowing conversion of 'st.std::pair<int, int>::first' from 'int' to 'short int' [-Wnarrowing]
   74 |     pq.push({st.first, st.second, 1, 0});
      |              ~~~^~~~~
soccer.cpp:74:27: warning: narrowing conversion of 'st.std::pair<int, int>::second' from 'int' to 'short int' [-Wnarrowing]
   74 |     pq.push({st.first, st.second, 1, 0});
      |                        ~~~^~~~~~
soccer.cpp:84:51: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   84 |                 if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + u.koszt});
      |                                                   ^
soccer.cpp:85:51: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   85 |                 if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, B + A * abs(l - u.a) + u.koszt});
      |                                                   ^
soccer.cpp:88:51: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   88 |                 if(odl[l][u.b][0] == -1) pq.push({l, u.b, 0, C * abs(l - u.a) + C * odl2[u.a][u.b] + u.koszt});
      |                                                   ^
soccer.cpp:89:51: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   89 |                 if(odl[l][u.b][1] == -1) pq.push({l, u.b, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.a) + u.koszt});
      |                                                   ^
soccer.cpp:95:56: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   95 |                 if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + u.koszt});
      |                                                        ^
soccer.cpp:96:56: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   96 |                 if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, B + A * abs(l - u.b) + u.koszt});
      |                                                        ^
soccer.cpp:99:56: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   99 |                 if(odl[u.a][l][0] == -1) pq.push({u.a, l, 0, C * abs(l - u.b) + C * odl2[u.a][u.b] + u.koszt});
      |                                                        ^
soccer.cpp:100:56: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
  100 |                 if(odl[u.a][l][1] == -1) pq.push({u.a, l, 1, C * odl2[u.a][u.b] + B + A * abs(l - u.b) + u.koszt});
      |                                                        ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65