제출 #1195672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195672		pete555	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	1897 ms	327680 KiB

commuter_pass

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

#define pi pair<int,int>
#define ll long long
#define pb push_back
#define pf push_front

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

const int N = 100005;

vector<pi> adj[N];
ll du[N], dv[N], ds[N];
ll dpu[N], dpv[N], ans;
int n, m, s, t, u, v;

void dijkstra(int u, ll d[]) {
	fill(d, d + N, LLONG_MAX / 2);

	priority_queue<pair<ll, int>> pq;
	pq.push({d[u] = 0, u});
	while(!pq.empty()) {
		auto [cdist, u] = pq.top();
		pq.pop();
		cdist *= -1;
		if(cdist > d[u]) continue;
		for(const auto [v, w] : adj[u]) {
			ll new_len = cdist + w;
			if(new_len < d[v]) {
				d[v] = new_len;
				pq.push({-d[v], v});
			}
		}
	}
}

void dijkstra2(int start, int end) {
	fill(dpu, dpu + N, LLONG_MAX / 2);
	fill(dpv, dpv + N, LLONG_MAX / 2);
	fill(ds, ds + N, LLONG_MAX / 2);

	priority_queue<pair<ll, pair<int, int>>> pq;
	pq.push({ds[start] = 0, {start, 0}});

	while(!pq.empty()) {
		ll cdist = pq.top().first;
		auto [u, par] = pq.top().second;
		pq.pop();
		cdist *= -1;
		if(cdist > ds[u]) continue;

		dpu[u] = min(du[u], dpu[par]);
		dpv[u] = min(dv[u], dpv[par]);

		for(const auto [v, w] : adj[u]) {
			ll new_len = ds[u] + w;
			if(new_len <= ds[v]) {
				ds[v] = new_len;
				pq.push({-ds[v], {v, u}});
			}
		}
	}
	ans = min(ans, dpu[end] + dpv[end]);
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	//fileIO("");
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		adj[a].pb({b, w});
		adj[b].pb({a, w});
	}
	dijkstra(u, du);
	dijkstra(v, dv);

	ans = du[v];

	dijkstra2(s, t);
	dijkstra2(t, s);

	cout << ans << '\n';
}

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

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

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