제출 #834305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834305		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	259 ms	35292 KiB

commuter_pass

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define INF INT_MAX
#define ENF INT_MIN
#define llINF 1e17
#define loop(i,n) for(int i=1 ; i<=n ; i++)
#define loop0(i,n) for(int i=0 ; i<n ; i++)
#define debug(arr, n) for(int i=1 ; i<=n ; i++) cout << i << ": " << arr[i] << endl;
#define debug0(arr, n) for(int i=0 ; i<n ; i++) cout << i << ": " << arr[i] << endl;
#define mem(a,b) memset(a, b, sizeof(a))
#define pllll pair<ll,ll>
#define OUT(x) if(x) cout << "YES\n"; else cout << "NO\n";

using namespace std;
const int N = 1e5 + 5;

ll n,m,s,t,u,v;
vector<pllll> adj[N];
ll dist[N], du[N], dv[N];
set<ll> par[N];
bool vis[N];
ll ans=llINF;
pllll dp[N];

//void dfs(ll curr, ll minu, ll minv){
////	if(vis[curr])return;
//	if(curr==s){
//		ans = min(ans, minu+minv);
//	}
//	for(auto i:par[curr]) dfs(i, min(minu, du[i]), min(minv, dv[i]));
//}

//ll dfs(ll curr){
//	if(curr==s) return du[curr] + dv[curr];
//	for(auto i:par[curr]) return min(du[curr], dfs(i)) + min(dv[curr], dfs(i));
//}

pllll dfs(ll curr){
	if(dp[curr].first!=-1) return dp[curr];
	if(curr==s) return {du[curr] , dv[curr]};
	for(auto i:par[curr]) return dp[curr] = {min(du[curr], dfs(i).first), min(dv[curr], dfs(i).second)};
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> s >> t >> u >> v;
	loop(i,m){
		ll t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		adj[t1].pb({t2,t3});
		adj[t2].pb({t1,t3});
	}
	
	//cari shortestpath dari u ke v
	loop(i,n)dist[i] = llINF;
	dist[s] = 0;
	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,s});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != dist[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c == dist[to]){
				par[to].insert(currnode);
			}
			else if(currdist + c < dist[to]){
				par[to].clear();
				par[to].insert(currnode);
				dist[to] = dist[currnode]+c;
				pq.push({dist[to], to});
			}
		}
	}

	//djikstra dari u
	loop(i,n)du[i] = llINF;
	du[u] = 0;
//	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,u});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != du[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c < du[to]){
				du[to] = du[currnode]+c;
				pq.push({du[to], to});
			}
		}
	}
//	loop(i,n) cout << du[i] << endl;

	//djikstra dari v
	loop(i,n)dv[i] = llINF;
	dv[v] = 0;
//	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,v});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != dv[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c < dv[to]){
				dv[to] = dv[currnode]+c;
				pq.push({dv[to], to});
			}
		}
	}
//	loop(i,n) cout << dv[i] << endl;

	ans = min(ans, du[v]);
	
//	loop(i,n) vis[i] = false;
//	dfs(t, du[t], dv[t]);

//	ans = min(ans, dfs(t));

	loop(i,n) dp[i] = {-1,-1};
	pllll temp = dfs(t);
	ans = min(ans, temp.first+temp.second);
	
	cout << ans << endl;
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'std::pair<long long int, long long int> dfs(long long int)':
commuter_pass.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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