Submission #1074046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074046		mmdrzada	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	443 ms	31568 KiB

commuter_pass

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

typedef long long ll;
typedef pair<int, int> pii;

#define sep ' '
#define fastIO 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int N = 1e5+100;
const ll LLINF = 2e18;
int n, m, s, t, x, y;
vector<pii> adj[N];
ll dis[N];
int par[N];
set<pair<int, int>> frees;
signed main() {
	fastIO;
	cin >> n >> m;
	cin >> s >> t;
	cin >> x >> y;
	s--, t--, x--, y--;
	for(int i = 0 ; i < m ; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[--v].push_back({--u, w});
		adj[u].push_back({v, w});
	}
	set<pair<ll, pii>> q;
	fill(dis, dis+n, LLINF);
	dis[s] = 0, par[s] = -1;
	for(auto [u, w]: adj[s]) q.insert({w, {s, u}});
	while(q.size()) {
		ll x = q.begin() -> first;
		auto [p, v] = q.begin() -> second;
		q.erase(q.begin());
		if (dis[v] != LLINF) continue;
		dis[v] = x;
		par[v] = p;
		for(auto [u, w]: adj[v]) {
			q.insert({0ll+w+x, {v, u}});
		}
	}
	while(par[t] != -1) {
		int k = par[t];
		frees.insert({t, k});
		frees.insert({k, t});
		t = k;
	}
	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < adj[i].size(); j ++)
			if (frees.find({i, adj[i][j].F}) != frees.end())
				adj[i][j].S = 0;
			
	set<pair<ll, int>> q2;
	fill(dis, dis+n, LLINF);
	dis[x] = 0;
	for(auto [u, w]: adj[x])
		q2.insert({w, u});
	
	while(q2.size()) {
		auto [x, v] = *q2.begin();
		q2.erase(q2.begin());
		if (dis[v] != LLINF) continue;
		dis[v] = x;
		for(auto [u, w]: adj[v])
			q2.insert({0ll+w+x, u});
	}
	cout << dis[y] << endl;
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j = 0 ; j < adj[i].size(); j ++)
      |                   ~~^~~~~~~~~~~~~~~

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