Submission #939781

#	Time	Username	Problem	Language	Result	Execution time	Memory
939781		mansur	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	371 ms	82444 KiB

commuter_pass

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 1e6 + 1, mod = 1e9 + 7;

const ll inf = 1e18;
 
double eps = 1e-15;
                                                
bool flg = 0;

vector<pll> g[N];
ll d[4][N];

void djk(int x, int tp) {
	set<pll> s;
	d[tp][x] = 0;
	s.insert({0, x});
	while (sz(s)) {
		x = (*s.begin()).s;
		s.erase(s.begin());
		for (auto [to, w]: g[x]) {
			if (d[tp][to] <= d[tp][x] + w) continue;
			s.erase({d[tp][to], to});
			d[tp][to] = d[tp][x] + w;
			s.insert({d[tp][to], to});
		}
	}
}

vector<int> gr[N], was(N), ord;

void dfs(int u) {
    was[u] = 1;
    for (int to: gr[u]) {
        if (!was[to]) dfs(to);
    }	
    ord.push_back(u);
}	

void slv() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 4; j++)
			d[j][i] = inf;
	}
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	int a[m + 1], b[m + 1], c[m + 1];
	for (int i = 1; i <= m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
	}
	djk(s, 0);
	djk(t, 1);
	djk(u, 2);
	djk(v, 3);
	ll L = d[0][t];
	for (int i = 1; i <= m; i++) {
		if (d[0][a[i]] + d[1][b[i]] + c[i] == L) {
		    //cout << a[i] << ' ' << b[i] << '\n';
			gr[b[i]].push_back(a[i]);
		}
		if (d[0][b[i]] + d[1][a[i]] + c[i] == L) {
		    //cout << b[i] << ' ' << a[i] << '\n';
			gr[a[i]].push_back(b[i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (sz(gr[i]) && !was[i]) dfs(i);
	}
	//cout << '\n';
	vector<ll> dp1(n + 1, inf), dp2(n + 1, inf);
	ll ans = d[2][v];
	for (int x: ord) {
		dp1[x] = d[2][x];
		dp2[x] = d[3][x];
		for (int to: gr[x]) {
			dp1[x] = min(dp1[x], dp1[to]);
			dp2[x] = min(dp2[x], dp2[to]);
		}
		//cout << x << ' ' << dp1[x] << ' ' << dp2[x] << '\n';
		ans = min(ans, d[3][x] + dp1[x]);
		ans = min(ans, d[2][x] + dp2[x]);
	}
	cout << ans;
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {
		//cout << "Case #" << cur++ << ": ";
		slv();
	}
}
//wenomechainsama                                              

Compilation message (stderr)

commuter_pass.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main() {
      | ^~~~

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