제출 #1169360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169360		vibeduck	Relay Marathon (NOI20_relaymarathon)	C++20	25 / 100	5305 ms	132500 KiB

RelayMarathon

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

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

int n, m, k;
vector<vector<pii>> adj; set<int> sp;

int dijkstra(int s, vi & d, vector<vector<pii>> & adj) {
    int n = adj.size();
    d.assign(n, inf);

    d[s] = 0;
    set<pll> q;
    q.insert({0, s}); int ans = -1;
    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        if ((sp.find(v) != sp.end()) && v != s) {
            ans = v;
            break;
        }

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                q.erase({d[to], to});
                d[to] = d[v] + len;
                q.insert({d[to], to});
            }
        }
    }

    return ans;
}

class DisjointSets {
    private:
 vector<int> parents;
 vector<int> sizes;

    public:
 DisjointSets(int size) : parents(size), sizes(size, 1) {
     for (int i = 0; i < size; i++) { parents[i] = i; }
 }

 int find(int x) {
     return parents[x] == x ? x : (parents[x] = find(parents[x]));
 }

 bool unite(int x, int y) {
     int x_root = find(x);
     int y_root = find(y);
     if (x_root == y_root) { return false; }

     if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
     sizes[x_root] += sizes[y_root];
     parents[y_root] = x_root;
     return true;
 }

 bool connected(int x, int y) { return find(x) == find(y); }
};


void dfs(int node, set<int> & comps, vi & vis) {
    vis[node] = 1;
    if (sp.find(node) != sp.end()) comps.insert(node);
    for (auto &neighbour : adj[node]) {
        if (vis[neighbour.fi]) continue;
        dfs(neighbour.fi, comps, vis);
    }
}

int solve(int x) {
    set<int> comps; vi vis(n); dfs(x, comps, vis); int ans = 1e18;
    for (auto it = comps.begin(); it != comps.end(); it++) {
        int u = *it;
        vi d(n); int v = dijkstra(u, d, adj);
        ans = min(ans, d[v]);
    }
    return ans;
}

inline void solve() {
    cin >> n >> m >> k;
    DisjointSets dsu(n); adj.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; 
        cin >> u >> v >> w;
        u--; v--;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        dsu.unite(u, v);
    }
    for (int i = 0; i < k; i++) {
        int x; cin >> x; x--;
        sp.insert(x);
    }
    
    int ans = 1e18;
    mii solved;
    for (int i = 2; i < n; i++) {
        int x = dsu.find(i);
        if (solved[x]) continue;
        ans = min(ans, solve(x));
        solved[x] = 1;
    }
    cout << 1 + ans << '\n';
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

RelayMarathon.cpp: In function 'void setIO(std::string)':
RelayMarathon.cpp:143:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:144:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 25 / 25
• Subtask 4: 0 / 58