Submission #932894

#	Time	Username	Problem	Language	Result	Execution time	Memory
932894		Oggy	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	169 ms	68056 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
const int N = 2e6 + 7;
const ll INF = 1e18;
int node, edge, trace[N], par2[N], par1[N], s, t, n, m;
vector<pll> adj[N];
queue<int> q;
bool vst[N];
ll dp[N];
// void run_with_file(){
// 	if(fopen(file".inp", "r")){
// 		freopen(file".inp", "r", stdin);
// 		freopen(file".out", "w", stdout);
// 	}
// }
void inp(){
	cin >> node >> edge;
	cin >> s >> t; 
	cin >> n >> m;
	for(int i = 1; i <= edge; ++i){
		int u, v;
		ll w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
}
void dijkstra(int x, int y, int par[]){
	vector<ll> d(node + 1, INF);
	d[x] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> Q;
	Q.push({d[x], x});
	while(!Q.empty()){
		pll top = Q.top(); Q.pop();
		int u = top.se;
		ll kc = top.fi;
		if(d[u] < kc) continue;
		for(auto it : adj[u]){
			int v = it.fi;
			ll w = it.se;
			if(d[v] > kc + w){
				d[v] = kc + w;
				trace[v] = u;
				Q.push({d[v], v});
			}
		}
	}
	while(x != y){
		par[y] = trace[y];
		y = trace[y];
	}
}
void bfs(int x){
	vst[x] = true;
	q.push(x);
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(auto it : adj[u]){
			int v = it.fi;
			ll w = it.se;
			if(!vst[v]){
				q.push(v);
				vst[v] = true;
				dp[v] = dp[u] + w * ((par2[v] == u || par1[v] == u) ? 0 : 1);
			}
			else{
				dp[v] = min(dp[v], dp[u] + w * ((par2[v] == u || par1[v] == u) ? 0 : 1));
			}
		}
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	// run_with_file();
	inp(); 
	dijkstra(s, t, par2);
	dijkstra(t, s, par1);
	bfs(n);
	cout << dp[m];
}

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