oj.uz

답안 #429696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429696 2021-06-16T08:47:50 Z 최서현(#7502) Brackets (CPSPC17_brackets) C++17
0 / 100
 5 ms 676 KB 
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define piii pair<int, pii>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss

using namespace std;

const int INF = (int)1e9 + 7;
vector<int> gph[202][8];
vector<int> rgph[202][8];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int n, m, s, e; cin >> n >> m >> s >> e; --s; --e;
    for(int i = 0; i < m; ++i)
    {
        int x, y; char c; cin >> x >> y >> c; --x; --y;
        int z;
        if(c == '<') z = 0;
        if(c == '>') z = 1;
        if(c == '{') z = 2;
        if(c == '}') z = 3;
        if(c == '[') z = 4;
        if(c == ']') z = 5;
        if(c == '(') z = 6;
        if(c == ')') z = 7;
        gph[x][z].push_back(y);
        rgph[y][z].push_back(x);
    }

    int C[n][n];
    for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) C[i][j] = INF;

    queue<piii> Q;
    for(int i = 0; i < n; ++i) Q.push({i, {i, 0}});
    while(Q.size())
    {
        auto x = Q.front(); Q.pop();
        if(C[x.ff][x.ee] != INF) continue;
        C[x.ff][x.ee] = x.rr;
        for(int i = 0; i < 8; i += 2)
        {
            for(auto j : rgph[x.ff][i])
            {
                for(auto k : gph[x.ee][i + 1])
                {
                    Q.push({j, {k, x.rr + 2}});
                }
            }
        }
    }

//    for(int i = 0; i < n; ++i)
//    {
//        for(int j = 0; j < n; ++j)
//            cout << C[i][j] << ' ';
//        cout << endl;
//    }

    int D[n]; bool F[n]{};
    for(int i = 0; i < n; ++i) D[i] = INF;
    D[s] = 0;

    for(int i = 0; i < n; ++i)
    {
        int mn = INF, mni;
        for(int j = 0; j < n; ++j) if(!F[j] && D[j] < mn) mn = D[j], mni = j;
        F[mni] = true;
        for(int j = 0; j < n; ++j) if(!F[j]) D[j] = min(D[j], D[mni] + C[mni][j]);
    }

    cout << (D[e] == INF ? -1 : D[e]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:79:68: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         for(int j = 0; j < n; ++j) if(!F[j]) D[j] = min(D[j], D[mni] + C[mni][j]);
      |                                                               ~~~~~^
Main.cpp:28:13: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         int z;
      |             ^

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -