Submission #753864

#	Time	Username	Problem	Language	Result	Execution time	Memory
753864		cwza	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	489 ms	22716 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
void IO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

const int maxN = 1e5;
const ll inf = 2e18;
int N, M, S, T, U, V;
vector<pair<int, int>> adj[maxN];

ll distU[maxN], distV[maxN], distS[maxN], distT[maxN];
void dijkstra(int s, ll dist[maxN]) {
    fill(dist, dist+N, inf);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(pq.size()) {
        auto [d, u] = pq.top(); pq.pop(); 
        if(d>dist[u]) continue;
        for(auto [v, w] : adj[u]) {
            if(dist[u]+w<dist[v]) {
                dist[v] = dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    }
}

bool visited[maxN];
ll dpU[maxN], dpV[maxN];
void dfs(int u) {
    visited[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(distS[u]+w+distT[v]!=distS[T]) continue;
        if(!visited[v]) dfs(v);
        if(min(distU[u], dpU[v])+min(distV[u], dpV[v]) < dpU[u]+dpV[u]) {
            dpU[u] = min(distU[u], dpU[v]);
            dpV[u] = min(distV[u], dpV[v]);
        }
    }
}

int main() {
    // IO("wormsort");

    cin >> N >> M >> S >> T >> U >> V;
    S--; T--; U--; V--;
    for(int i = 0, u, v, w; i < M; i++) {
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijkstra(U, distU);
    dijkstra(V, distV);
    dijkstra(S, distS);
    dijkstra(T, distT);

    fill(dpU, dpU+N, inf);
    fill(dpV, dpV+N, inf);
    dpU[T] = distU[T];
    dpV[T] = distV[T];
    dfs(S);
    cout << min(dpU[S]+dpV[S], distU[V]) << "\n";
}

Compilation message (stderr)

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

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