Submission #1224734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224734		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2 ms	4236 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const int MAXN = 1e5 + 5;

ll n, m, A, B, C, D;
vector<pll> adj[MAXN];
vector<ll> parent(MAXN, -1);
vector<ll> dist(MAXN, INF);
set<pair<ll, ll>> used_edges;  // Lưu các cạnh thuộc đường buổi sáng

void dijkstra(ll start, ll end) {
    fill(dist.begin(), dist.end(), INF);
    fill(parent.begin(), parent.end(), -1);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (u == end) break;
        if (d > dist[u]) continue;
        
        for (auto [v, c] : adj[u]) {
            if (dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

ll find_min_path_with_free_edges() {
    vector<ll> new_dist(n + 1, INF);
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    new_dist[C] = 0;
    pq.push({0, C});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (u == D) break;
        if (d > new_dist[u]) continue;
        
        for (auto [v, c] : adj[u]) {
            // Kiểm tra cạnh (u, v) có free không
            bool is_free = used_edges.count({min(u, v), max(u, v)});
            ll new_cost = d + (is_free ? 0 : c);
            
            if (new_cost < new_dist[v]) {
                new_dist[v] = new_cost;
                pq.push({new_dist[v], v});
            }
        }
    }
    
    return new_dist[D];
}

int main() {
    freopen("tunnel.inp", "r", stdin);
    freopen("tunnel.out", "w", stdout);
    
    cin >> n >> m;
    cin >> A >> B >> C >> D;
    
    for (int i = 0; i < m; i++) {
        ll u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }
    
    // Bước 1: Tìm đường ngắn nhất A → B
    dijkstra(A, B);
    
    // Lưu các cạnh thuộc đường buổi sáng
    ll current = B;
    while (current != A && current != -1) {
        ll prev = parent[current];
        used_edges.insert({min(prev, current), max(prev, current)});
        current = prev;
    }
    
    // Bước 2: Tìm đường ngắn nhất C → D với cạnh free
    ll result = find_min_path_with_free_edges();
    
    cout << result << endl;
    
    return 0;
}

Compilation message (stderr)

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

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