Submission #1233772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233772		nguyenphong233	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	257 ms	36776 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],cf[MAX];
int res = INF;
int dp[MAX][2];
vector<int> rt;
void topo(int u = s,int p = 0){
	cf[u] = 1;
	for(auto v : g[u]){
		assert(v != p);
		if(cf[v])continue;
		topo(v,u);
	}
	rt.push_back(u);
}
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]});
	
	topo();
	for(int i = 1;i <= n;i++){
		if(cf[i] == 0)rt.push_back(i);
	}
	
	for(int i = 0;i < n;i++){
		int u = rt[i];
		dp[u][0] = min(dp[u][0],dist[u][1]);
		dp[u][1] = min(dp[u][1],dist[u][2]);
		
		for(auto v : g[u]){
			dp[u][0] = min(dp[u][0],dp[v][0]);
			dp[u][1] = min(dp[u][1],dp[v][1]);
		}
		
		res = min({res,dp[u][0] + dist[u][2],dp[u][1] + dist[u][1]});
	}
	//for(auto v : rt)cout << v << " :\n";
	cout << res;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:92:34: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   92 |                         dp[i][j] = INF;
      |                         ~~~~~~~~~^~~~~
commuter_pass.cpp:91:33: note: within this loop
   91 |                 for(int j = 0;j < 3;j++){
      |                               ~~^~~

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