제출 #1190496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190496		zh_h	자매 도시 (APIO20_swap)	C++17	17 / 100	1983 ms	589824 KiB

swap

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

vector<vector<pair<int, int>>> edge;
vector<vector<int>> cost;
int N;

void init (int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    edge.resize(n+1);
    for (int i = 0; i < m; i ++) {
        edge[u[i]].pb({v[i], w[i]});
        edge[v[i]].pb({u[i], w[i]});
    }

    N = n;
}

int getMinimumFuelCapacity (int x, int y) {
    cost.clear();
    cost.resize(N+1, vector<int>(N+1, 1e9+1));

    priority_queue<pair<int, pair<int, int>>> q;
    vector<vector<int>> visited(N+1, vector<int>(N+1, false));
    cost[x][y] = 0;

    q.push({0, {x, y}});

    while (!q.empty()) {
        int w = -q.top().first;
        int a = q.top().second.first, b = q.top().second.second;
        q.pop();

        if (visited[a][b]) continue;
        visited[a][b] = true;

        for (auto i : edge[a]) {
            if (i.first == b) continue;

            int new_w = max(w, i.second);
            if (new_w < cost[i.first][b]) {
                cost[i.first][b] = new_w;
                q.push({-new_w, {i.first, b}});
            }
        }

        for (auto i : edge[b]) {
            if (i.first == a) continue;

            int new_w = max(w, i.second);
            if (new_w < cost[a][i.first]) {
                cost[a][i.first] = new_w;
                q.push({-new_w, {a, i.first}});
            }
        }
    }
    
    if (cost[y][x] == 1e9+1) cost[y][x] = -1;
    return cost[y][x];;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27