Submission #788576

#	Time	Username	Problem	Language	Result	Execution time	Memory
788576		ooscode	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	361 ms	41548 KiB

commuter_pass

// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define scan scanf
#define print printf
#define outs(x) print("%lld " , x)
#define out(x) print("%lld\n" , x)
#define in(x) scan("%lld" , &x)
#define int ll
#define kids int tm = (tl + tr)/2; int cl = 2*v; int cr = 2*v+1

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii,int> piii;
typedef pair<pll , ll> plll;
 
const int N = 1e5+10;
const int K = 70+10;
const ll mod = 998244353;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

vector<pii> g[N];
vector<pii> gr[N];
vector<pii> rg[N];

int dp[N];
int pd[N];

int n , m;
int s , t;
int x , y;

int dis[5][N];

int mark[N];

pair<pii , int> edg[2*N];

vector<int> vec , ve; 

void dfs(int v) {
	mark[v] = 1;
	for(auto u : gr[v])
		if(!mark[u.F])
			dfs(u.F);
	vec.pb(v);
}

void topol() {
	for(int i = 1 ; i <= ve.size() ; i++)
		if(!mark[ve[i-1]])
			dfs(ve[i-1]);
	reverse(all(vec));
}

void dij(int v , int t) {
	priority_queue<pii , vector<pii> , greater<pii>> pq;
	dis[t][v] = 0;
	pq.push({0 , v});

	while(pq.size()) {
		int v = pq.top().S;
		int ww = pq.top().F;

		pq.pop();

		if(ww != dis[t][v])
			continue;
		
		for(auto u : g[v])
			if(dis[t][u.F] > dis[t][v] + u.S) {
				dis[t][u.F] = dis[t][v] + u.S;
				pq.push({dis[t][u.F] , u.F});
			}
	}
}

void solve() 
{
	cin >> n >> m >> s >> t >> x >> y;
	for(int i = 1 ; i <= m ; i++) {
		int v , u , w;
		cin >> v >> u >> w;
		g[v].pb({u , w});
		g[u].pb({v , w});
		edg[i] = {{v , u} , w};
	}

	for(int i = 1 ; i <= 4 ; i++)
		for(int j = 1 ; j <= n ; j++)
			dis[i][j] = INF;

	dij(s , 1);
	dij(t , 2);
	dij(x , 3);
	dij(y , 4);

	for(int i = 1 ; i <= m ; i++) {
		int v = edg[i].F.F;
		int u = edg[i].F.S;
		int w = edg[i].S;

		if(dis[1][v] + w + dis[2][u] == dis[1][t]) {
			gr[v].pb({u , w});
			rg[u].pb({v , w});
			
			if(!mark[v]) {
				mark[v] = 1;
				ve.pb(v);
			}

			if(!mark[u]) {
				mark[u] = 1;
				ve.pb(u);
			}
		}
		if(dis[1][u] + w + dis[2][v] == dis[1][t]) {
			gr[u].pb({v , w});
			rg[v].pb({u , w});
			
			if(!mark[v]) {
				mark[v] = 1;
				ve.pb(v);
			}

			if(!mark[u]) {
				mark[u] = 1;
				ve.pb(u);
			}
		}
	}

	for(int i = 1 ; i <= n ; i++)
		mark[i] = 0;

	topol();

	int ans = INF;

	for(auto v : vec) {
		dp[v] = dis[3][v];
		for(auto u : rg[v])
			dp[v] = min(dp[v] , dp[u.F]);
		
		ans = min(ans , dp[v] + dis[4][v]);
	}

	for(int i = vec.size()-1 ; i >= 0 ; i--) {
		int v = vec[i];
		pd[v] = dis[3][v];
		for(auto u : gr[v])
			pd[v] = min(pd[v] , pd[u.F]);

		ans = min(ans , pd[v] + dis[4][v]);
	}

	cout << min(ans , dis[3][y]) << "\n";
}

signed main() 
{
	int n = 1;
	// cin >> n;
	while(n--)
		solve();
}

// CODE = LOVE 
// IT'S EASY TO SEE

Compilation message (stderr)

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

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