oj.uz

Submission #565528

# Submission time Handle Problem Language Result Execution time Memory
565528 2022-05-21T04:15:00 Z lohacho Wild Boar (JOI18_wild_boar) C++14
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

vector<vector<vector<int>>> dijkstra(int s, vector<vector<pair<int, int>>>&way){
    vector<vector<vector<int>>> rv((int)way.size(), vector<vector<int>>(4, vector<int>{-1, -1, -1}));
    priority_queue<vector<int>> pq;
    for(auto&nxt:way[s]){
        pq.push({-nxt.second, nxt.first, s, nxt.first});
    }
    while(!pq.empty()){
        int val = -pq.top()[0], ns = pq.top()[1], ne = pq.top()[2], now = pq.top()[3];
        pq.pop();
        int vpos = 0;
        if(rv[now][0][0] != -1){
            vpos = (rv[now][0][0] != ns) * 2 + (rv[now][0][1] != ne);
        }
        if(rv[now][vpos][0] != -1) continue;
        rv[now][vpos] = {ns, ne, val};
        for(auto&nxt:way[now]){
            if(nxt.first != ne){
                pq.push({-(val + nxt.second), ns, now, nxt.first});
            }
        }
    }
    return rv;
}

vector<vector<vector<int>>> dijkstra2(int s, vector<vector<pair<int, int>>>&way){
    vector<vector<vector<int>>> rv((int)way.size(), vector<vector<int>>(4, vector<int>{-1, -1, -1}));
    priority_queue<vector<int>> pq;
    for(auto&nxt:way[s]){
        pq.push({-nxt.second, nxt.first, -2, nxt.first});
    }
    while(!pq.empty()){
        int val = -pq.top()[0], ns = pq.top()[1], ne = pq.top()[2], now = pq.top()[3];
        pq.pop();
        int vpos = 0;
        if(rv[now][0][0] != -1){
            vpos = (rv[now][0][0] != ns) * 2 + (rv[now][0][1] != ne);
        }
        if(rv[now][vpos][0] != -1) continue;
        rv[now][vpos] = {ns, ne, val};
        for(auto&nxt:way[now]){
            if(nxt.first != ne){
                pq.push({-(val + nxt.second), ns, now, nxt.first});
            }
        }
    }
    return rv;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, t, l; cin >> n >> m >> t >> l;
    vector<vector<pair<int, int>>> way(n);
    for(int i = 0; i < m; ++i){
        int x, y, z; cin >> x >> y >> z; --x, --y;
        way[x].push_back({y, z});
        way[y].push_back({x, z});
    }
    vector<vector<vector<vector<int>>>> dis(n);
    for(int i = 0; i < n; ++i){
        dis[i] = dijkstra(i, way);
    }
    vector<int> trk(l);
    for(int i = 0; i < l; ++i){
        cin >> trk[i]; --trk[i];
    }
    int x, y; cin >> x >> y; --x, --y;
    trk[x] = y;
    vector<vector<int>> dp(l, vector<int>(4, (int)1e18));
    vector<vector<vector<int>>> dtz = dijkstra2(trk[0], way);
    for(int i = 0; i < 4; ++i){
        dp[1][i] = dtz[trk[1]][i][2];
    }
    for(int i = 1; i + 1 < l; ++i){
        for(int j = 0; j < 4; ++j){
            for(int k = 0; k < 4; ++k){
                if(dis[trk[i - 1]][trk[i]][j][0] != -1 && dis[trk[i]][trk[i + 1]][k][0] != -1){
                    if(dis[trk[i - 1]][trk[i]][j][1] != dis[trk[i]][trk[i + 1]][k][0]){
                        mi(dp[i + 1][k], dp[i][j] + dis[trk[i]][trk[i + 1]][k][2]);
                    }
                }
            }
        }
    }
    int ans = (int)1e18;
    for(int i = 0; i < 4; ++i){
        mi(ans, dp[l - 1][i]);
    }
    if(ans == (int)1e18) ans = -1;
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -