제출 #1248810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248810		CodeLakVN	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2097 ms	23184 KiB

commuter_pass

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

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define li pair<long long, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)1e5 + 5;
const long long INF = (long long)1e18;

int numNode, numEdge;
int startSchool, endSchool, startStore, endStore;
vector<ii> adj[MAX_N];

vector<long long> dist[3]; // minimum paths from s, u, v -> i (i = 1..n)
vector<int> dag[MAX_N], trace[MAX_N];

void dijkstra(vector<long long> &dist, int s, bool isTrace) {
    dist.assign(numNode + 1, INF);
    dist[s] = 0;
    priority_queue<li, vector<li>, greater<li>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().S;
        pq.pop();
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
                if (isTrace) {
                    trace[v].clear();
                    trace[v].push_back(u);
                }
            }
            else if (dist[v] == dist[u] + w && isTrace) {
                trace[v].push_back(u);
            }
        }
    }
}

bool vis[MAX_N];

void dfs(int u) {
    if (vis[u] || u == startSchool) return;
    vis[u] = 1;
    for (int v : trace[u]) {
        dag[v].push_back(u);
        dfs(v);
    }
}

// dpIn: v -> x -> y -> u, dpOut: u -> x -> y -> v, with x, y is a sub-path of the optimal path from s -> t
long long dpIn[MAX_N], dpOut[MAX_N];

void calc(int u) {
    if (u == endSchool) return;
    dpOut[u] = dist[2][u];
    for (int v : dag[u]) {
        dpIn[v] = min(dist[2][v], dpIn[u]);
        calc(v);
        dpOut[u] = min(dpOut[u], dpOut[v]);
    }
}

void solve() {
    cin >> numNode >> numEdge >> startSchool >> endSchool >> startStore >> endStore;
    FOR(i, 1, numEdge) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijkstra(dist[0], startSchool, 1);
    dijkstra(dist[1], startStore, 0);
    dijkstra(dist[2], endStore, 0);

    dfs(endSchool);

    long long ans = dist[1][endStore]; // just go from u -> v
    FOR(i, 0, numNode) dpIn[i] = dpOut[i] = INF;
    dpIn[startSchool] = dist[2][startSchool];
    dpOut[endSchool] = dist[2][endSchool];
    calc(startSchool);

    FOR(i, 1, numNode) ans = min(ans, dist[1][i] + min(dpIn[i], dpOut[i]));

    cout << ans << "\n";
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

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

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

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

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45