Submission #24323984


Source Code Expand

Copy
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stdint.h>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
const int D = 4;
int dr[D] = {0, 1 , 0 , -1};
int dc[D] = {1, 0 , -1, 0};
struct Cell
{
int r;
int c;
Cell(int r_, int c_) : r(r_) , c(c_) {};
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stdint.h>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;

const int D = 4;
int dr[D] = {0, 1 , 0 , -1};
int dc[D] = {1, 0 , -1, 0};

struct Cell
{
    int r;
    int c;

    Cell(int r_, int c_) : r(r_) , c(c_) {};

    bool isWithinGrid(int nr, int nc)
    {
        return 0 <= r && r < nr &&
               0 <= c && c < nc;
    }
};

struct Solution
{
    int h;
    int w;
    int c;
    int64_t res;
    vector<vector<int> > a;
    vector<Cell> x;

    Solution()
    {
        Input();
        res = 1e18;
        for(int i = 0; i < (int) x.size(); i++)
        {
            bfs(x[i]);
        }

        cout << res << "\n";
    }

    void Input()
    {
        cin >> h >> w >> c;
        a.resize(h, vector<int>(w));
        int min_ = 1e9 + 1;
        for(int i = 0;i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                cin >> a[i][j];
                min_ = min(min_, a[i][j]);
            }
        }

        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(a[i][j] == min_) x.push_back(Cell(i, j));
            }
        }
    }

    void bfs(Cell s)
    {
        queue<Cell> q;
        vector<vector<bool> > visited(h, vector<bool>(w, false));
        q.push(s);

        while(!q.empty())
        {
            Cell u = q.front();
            visited[u.r][u.c] = true;
            q.pop();

            for(int i = 0;i < D; i++)
            {
                Cell v(u.r + dr[i], u.c + dc[i]);
                if(!v.isWithinGrid(h, w)) continue;
                if(visited[v.r][v.c]) continue;

                q.push(v);

                int64_t cal = a[s.r][s.c] + a[v.r][v.c]
                + (int64_t) c * (Abs(s.r - v.r) + Abs(s.c - v.c));

                res = min(res, cal);
            }
        }
    }

    int Abs(int val)
    {
        if(val < 0) return -val;
        return val;
    }
};

void _setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

int main() {
    _setup();

    Solution s;

    return 0;
}

Submission Info

Submission Time
Task D - National Railway
User Voltair
Language C++ (GCC 9.2.1)
Score 0
Code Size 2262 Byte
Status WA
Exec Time 2233 ms
Memory 779536 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 3
WA × 2
TLE × 29
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt TLE 2233 ms 777936 KB
001.txt TLE 2233 ms 775360 KB
002.txt TLE 2233 ms 779536 KB
003.txt TLE 2232 ms 757900 KB
004.txt TLE 2233 ms 776440 KB
005.txt TLE 2233 ms 777476 KB
006.txt TLE 2232 ms 756824 KB
007.txt TLE 2232 ms 768524 KB
008.txt TLE 2232 ms 759212 KB
009.txt TLE 2232 ms 749692 KB
010.txt TLE 2232 ms 748172 KB
011.txt TLE 2232 ms 738640 KB
012.txt TLE 2232 ms 747328 KB
013.txt TLE 2231 ms 747372 KB
014.txt TLE 2232 ms 746100 KB
015.txt TLE 2232 ms 748952 KB
016.txt TLE 2232 ms 741472 KB
017.txt TLE 2232 ms 745792 KB
018.txt TLE 2232 ms 746152 KB
019.txt TLE 2232 ms 746356 KB
020.txt TLE 2232 ms 761244 KB
021.txt TLE 2232 ms 759512 KB
022.txt TLE 2232 ms 766364 KB
023.txt TLE 2231 ms 702724 KB
024.txt TLE 2232 ms 766696 KB
025.txt AC 8 ms 3532 KB
026.txt WA 15 ms 3664 KB
027.txt WA 12 ms 3612 KB
028.txt TLE 2232 ms 762720 KB
029.txt TLE 2232 ms 757880 KB
030.txt TLE 2232 ms 743560 KB
031.txt TLE 2232 ms 735860 KB
example0.txt AC 8 ms 3476 KB
example1.txt AC 2 ms 3564 KB


2025-02-28 (Fri)
11:22:05 +00:00