Submission #1144472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144472		quangnamoiracvl_ralaidecu	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	257 ms	27372 KiB

commuter_pass

// // Author : Thao Nguyen Xinh 
// // Codeforces Handle : thaonguyendethuongvai
// #include<bits/stdc++.h> 
// using namespace std; 
// #define endl "\n" 
// #define tn long long 
// #define fi first 
// #define se second 
// #define pair pair< tn, tn > 
// #define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ ) 
// #define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- ) 
// #define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
// const tn N = 1e5 + 5;
// struct mimi{
//     tn u, w, a, b; 
// };
// struct cmp{
//     bool operator()( const mimi a, const mimi b ){
//         return a.w < b.w; 
//     }
// };
// vector< pair > g[N];  
// tn n, m, w, a, b, s, t, u, v, result = 1e18, dist[N][2]; 
// mimi dick[N];
// priority_queue< mimi, vector< mimi >, cmp > Q;
// priority_queue< pair, vector< pair >, greater< pair > > q;  
// void dijkstra( tn start, tn type ){
//     dist[start][type] = 0; 
//     q.push( { 0, start } ); 
//     while(!q.empty() ){
//         u = q.top().se;  
//         tn cost = q.top().fi; 
//         q.pop(); 
//         if ( cost > dist[u][type] ) 
//             continue;
//         for ( auto v : g[u] ){
//             if ( dist[v.fi][type] > cost + v.se ){
//                 dist[v.fi][type] = cost + v.se;
//                 q.push( { dist[v.fi][type], v.fi } );
//             }
//         }
//     }
// }
// void bfs(){
//     freopen( "thao_nguyen_trong_tim_toan.inp", "r", stdin ); 
//     freopen( "thao_nguyen_trong_tim_toan.out", "w", stdout );
//     dick[s].w = 0; dick[s].a = dist[s][0]; dick[s].b = dist[s][1]; 
//     result = min( result, dick[s].a + dick[s].b ); 
//     q.push( { 0, s } ); 
//     while ( !q.empty() ){
//         tn u = q.top().se; 
//         tn cost = q.top().fi;
//         q.pop(); 
//         if ( cost > dick[u].w )
//             continue; 
//         for ( auto v : g[u] ){
//             if ( dick[v.fi].w > dick[u].w + v.se ){
//                 dick[v.fi].w = dick[u].w + v.se; 
//                 dick[v.fi].a = min( dick[u].a, dist[v.fi][0] ); 
//                 dick[v.fi].b = min( dick[u].b, dist[v.fi][1] );
//                 q.push( { dick[v.fi].w, v.fi } );  
//             }
//             else if ( dick[v.fi].w == dick[u].w + v.se ){
//                 if ( dick[v.fi].a + dick[v.fi].b > dick[u].a + dick[u].b ) 
//                     dick[v.fi].a = dick[u].a, 
//                     dick[v.fi].b = dick[u].b;
//             }
//         }
//     }   
// }
// signed main(){
    
//     thaonguyenxinh 
//     // hi skibidi 
//     cin >> n >> m >> s >> t >> a >> b;
//     thaonguyen( i, 1, n ) 
//         dist[i][0] = dist[i][1] = dist[i][2] = dick[i].w = 1e18;
//     thaonguyen( i, 1, m ){
//         cin >> u >> v >> w;
//         g[u].push_back( { v, w } );
//         g[v].push_back( { u, w } );
//     }
//     dijkstra( a, 0 ); dijkstra( b, 1 ); bfs(); 
//     cout << dist[a][1] << endl; 
//     cout << min( dist[a][1], dick[t].a + dick[t].b ); 
// }
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<pair<ll, ll>> graph[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;
bool visited[100001];

void dijkstra1(ll start, ll arr[]) {
	fill(visited, visited + 100001, false);

	priority_queue<pair<ll, ll>> pq;
	pq.push({0, start});
	while (!pq.empty()) {
		ll c, node;
		tie(c, node) = pq.top();
		pq.pop();

		if (!visited[node]) {
			arr[node] = -c;
			visited[node] = true;
			for (auto &i : graph[node]) pq.push({c - i.second, i.first});
		}
	}
}

void dijkstra2(ll start, ll end) {
	fill(dp[0], dp[0] + 100001, LLONG_MAX / 2);
	fill(dp[1], dp[1] + 100001, LLONG_MAX / 2);
	fill(visited, visited + 100001, false);

	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push({0, {start, 0}});
	dp[0][0] = dp[1][0] = LLONG_MAX / 2;
	while (!pq.empty()) {
		ll c, node, par;
		pair<ll, ll> p;
		tie(c, p) = pq.top();
		tie(node, par) = p;
		pq.pop();

		if (!visited[node]) {
			visited[node] = true;
			ds[node] = -c;
			dp[0][node] = min(du[node], dp[0][par]);
			dp[1][node] = min(dv[node], dp[1][par]);
			for (auto i : graph[node]) pq.push({c - i.second, {i.first, node}});
		} else if (-c == ds[node]) {
			if (min(du[node], dp[0][par]) + min(dv[node], dp[1][par]) <=
			    dp[0][node] + dp[1][node]) {
				dp[0][node] = min(du[node], dp[0][par]);
				dp[1][node] = min(dv[node], dp[1][par]);
			}
		}
	}

	ans = min(ans, dp[0][end] + dp[1][end]);
}

int main() {
    
	iostream::sync_with_stdio(false);
	cin.tie(0);
	ll n, m, s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 0; i < m; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}

	dijkstra1(u, du);
	dijkstra1(v, dv);

	ans = du[v];
    //cout << ans << endl; 
	dijkstra2(s, t);
	//dijkstra2(t, s);

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

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