Submission #743243

#	Time	Username	Problem	Language	Result	Execution time	Memory
743243		josanneo22	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	2056 ms	28732 KiB

commuter_pass

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

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#define int long long
const int maxn = 1e5 + 5;
vector<vector<pii>> adj(maxn);
vector<int> d1(maxn, LLONG_MAX), d2(maxn, LLONG_MAX);
void bfs(int s,int chance) {
	queue<pii> q;
	q.push(mp(s,0));
	while (q.size()) {
		pii u = q.front(); q.pop();
		if (chance == 0) {
			if (d1[u.fi] <= u.se) continue;
			d1[u.first] = u.second;
			for (auto& v : adj[u.first]) {
				q.push(mp(v.first, u.second + v.second));
			}
		}
		else {
			if (d2[u.fi] <= u.se) continue;
			d2[u.first] = u.second;
			for (auto& v : adj[u.first]) {
				q.push(mp(v.first, u.second + v.second));
			}
		}
	}
	return;
}
vector<int> par, sz;
int total_groups;
void init(int n) {
	par.resize(n); sz.resize(n);
	for (int i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
}
int find(int x) {
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
	total_groups--;
}
bool same(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return true;
	else return false;
}
//remember to init(n+5) and total_groups=n

void solve() { 
	int n, m; cin >> n >> m;
	int s, t; cin >> s >> t;
	int st, en; cin >> st >> en;
	init(n + 5);
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}
	vector<int> path;
	bfs(s, 0); bfs(t, 1);
	for (int i = 1; i <= n; i++) {
		if (d1[i] + d2[i] == d1[t]) {
			path.push_back(i);
		}
	}
	for (int i = 0; i < path.size(); i++) {
		cout << path[i] << ' ';
	}
	for (int i = 1; i < path.size(); i++) {
		unite(path[i], path[i - 1]);
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push(mp(0,st));
	vector<int> ans(n+5, LLONG_MAX);
	while (pq.size()) {
		pii u = pq.top(); pq.pop();
		if (ans[u.second] <= u.first) continue;
		ans[u.second] = u.first;
		for (auto& v : adj[u.second]) {
			if (same(u.second, v.first)) {
				pq.push(mp(u.first, v.first));
			}
			else {
				pq.push(mp(u.first + v.second, v.first));
			}
		}
	}
	cout << ans[en] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:83:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 0; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~
commuter_pass.cpp:86:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 1; i < path.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

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