Submission #1233620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233620		nguyenphong233	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2097 ms	36944 KiB

commuter_pass

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)3e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;

int n,m;
vector<ii> adj[MAX];
int s,t,ux,vx;
vector<int> g[MAX];
int dist[MAX][3];
priority_queue<ii,vector<ii>,greater<ii>> q;
bool dd[MAX];
int res = INF;
int dp[MAX][3];

void calc(int u,int p,int x,int y){
	dp[u][x] = min(dist[u][x],dp[u][x]);
	for(auto v : g[u]){
		if(v == p)assert(v == p);
		dp[v][x] = dp[u][x];
		calc(v,u,x,y);
	}
	res = min(res,dp[u][x] + dist[u][y]);
}
void dijsktra(int st,int ct){
	for(int i = 1;i <= n;i++)dist[i][ct] = INF;
	q.push({0,st});
	dist[st][ct] = 0;
	
	while(!q.empty()){
		int u = q.top().Y;
		int c = q.top().X;
		q.pop();
		if(c != dist[u][ct])continue;
		for(auto e : adj[u]){
			int v = e.X;
			int w = e.Y;
			
			if(dist[v][ct] > dist[u][ct] + w){
				dist[v][ct] = dist[u][ct] + w;
				q.push({dist[v][ct],v});
			}
		}
	}
}
signed main(){
	
	cin >> n >> m >> s >> t >> ux >> vx;
	for(int i = 1,u,v,w;i <= m;i++){
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}	
	
	dijsktra(s,0);
	deque<int> h;
	h.push_back(t);
	dd[t] = 1;
	
	while(!h.empty()){
		int u = h.front();
		h.pop_front();
		for(auto e : adj[u]){
			if(dist[u][0] == dist[e.X][0] + e.Y){
				if(!dd[e.X]){
					dd[e.X] = 1;
					h.push_back(e.X);
				}
				g[e.X].push_back(u);
			}
		}
	}
	
	dijsktra(ux,1);
	dijsktra(vx,2);
	
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < 3;j++){
			dp[i][j] = INF;
		}
	}
	
	res = min({res,dist[ux][2],dist[vx][1]});
	calc(s,0,1,2);
	calc(s,0,2,1);
	cout << res;
}

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