제출 #414282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414282		prvocislo	자매 도시 (APIO20_swap)	C++17	0 / 100	2036 ms	25644 KiB

swap

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

const int maxn = 1005, inf = 1e9 + 5;
vector<vector<pair<int, int> > > g(maxn);
int n, m;
void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
  n = N, m = M;
  for (int i =0;i < m;i++) g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
}
int d[maxn][maxn];
int getMinimumFuelCapacity(int x, int y) {
  for (int i =0; i < n;i++) for (int j =0;j < n;j++) d[i][j] = inf;
  set<pair<int, pair<int, int> > > s;
  s.insert({0, {x, y}});
  while (!s.empty())
  {
    int u = s.begin()->second.first, v = s.begin()->second.second, dist = s.begin()->first;
    s.erase(s.begin());
    if (d[u][v] < dist) continue;
    d[u][v] = dist;
    for (pair<int, int> i : g[u])
    {
        int u2 = i.first, d2 = max(dist, i.second);
        if (u2 != v && d[u2][v] == inf) 
          s.insert({d2, {u2, v} });
    }
    for (pair<int, int> i : g[v])
    {
        int v2 = i.first, d2 = max(dist, i.second);
        if (v2 != u && d[u][v2] == inf) 
          s.insert({d2, {u, v2} });
    }
  }
  return d[y][x] == inf ? -1 : d[y][x];
}

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