Submission #391188

#	Time	Username	Problem	Language	Result	Execution time	Memory
391188		ritul_kr_singh	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	406 ms	24628 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAXN = 1e5, INF = 1e18;

vector<vector<pair<int, int>>> g(MAXN);
vector<int> distS(MAXN, INF), distT(MAXN, INF), distA(MAXN, INF), distB(MAXN, INF);

int n, m, s, t, a, b, x, y, z;

void dijkstra(int r, vector<int> &dist){
	priority_queue<pair<int, int>> q;
	dist[r] = 0;
	q.emplace(0, r);
	while(!q.empty()){
		int u = q.top().second, d = -q.top().first; q.pop();
		if(d != dist[u]) continue;
		for(auto &e : g[u]){
			int v = e.first, w = e.second;
			if(dist[v] > d + w){
				dist[v] = d + w;
				q.emplace(-(d + w), v);
			}
		}
	}
}


signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> s >> t >> a >> b;
	--s, --t, --a, --b;

	while(m--){
		cin >> x >> y >> z; --x, --y;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
	}

	dijkstra(s, distS);
	dijkstra(t, distT);
	dijkstra(a, distA);
	dijkstra(b, distB);

	int shortest = distS[t];

	vector<array<int, 2>> dp(n, {INF, INF});

	vector<pair<int, int>> onPath;
	for(int i=0; i<n; ++i){
		if(distS[i] + distT[i] == shortest) onPath.emplace_back(distS[i], i);
	}

	int ans = distA[b];

	sort(onPath.begin(), onPath.end());

	for(auto &i : onPath){
		int u = i.second;
		dp[u][0] = min(dp[u][0], distA[u]);
		dp[u][1] = min(dp[u][1], distB[u]);

		ans = min(ans, dp[u][0] + distB[u]);
		ans = min(ans, dp[u][1] + distA[u]);

		for(auto &e : g[u]){
			int v = e.first, w = e.second;
			dp[v][0] = min(dp[v][0], dp[u][0]);
			dp[v][1] = min(dp[v][1], dp[u][1]);
		}
	}

	cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:21: warning: unused variable 'w' [-Wunused-variable]
   70 |    int v = e.first, w = e.second;
      |                     ^

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