Submission #850250

#	Time	Username	Problem	Language	Result	Execution time	Memory
850250		hqminhuwu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	259 ms	37828 KiB

commuter_pass

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

priority_queue <pii, vector <pii>, greater <pii>> q;
queue <int> qq;
ll dis[5][N],mn = oo * oo,dp[2][N],ans = oo * oo;
int a,b,c,d,deg[N];
vector <pll> g[N];
vector <int> ng[N];

void calc (int s, int i){
	q.push({0,s});
	memset(dis[i],0x3f,sizeof dis[i]);
	dis[i][s] = 0;
	while (!q.empty()){
		pii u = q.top();
		q.pop();
		if (u.st > dis[i][u.nd])
			continue;
		for (pii v : g[u.nd])
		if (v.nd + u.st < dis[i][v.st])
			dis[i][v.st] = v.nd + u.st, q.push({dis[i][v.st],v.st});
	}
	if (i == 1)
		mn = dis[i][a];
}

void finalcalc(){
	qq.push(a);
	//memset (dp,0x3f,sizeof dp);
	while (!qq.empty()){
		int u = qq.front();
		qq.pop();
		ans = min (ans,min(dp[0][u] + dis[3][u],dp[1][u] + dis[2][u]));
		//cout << u << " " << dp[0][u] << " " << dp[1][u] << "\n";
		for (int v : ng[u]){
			dp[0][v] = min (dp[0][v],dp[0][u]);
			dp[1][v] = min (dp[1][v],dp[1][u]); 
			deg[v]--;
			if (deg[v] == 0)
				qq.push(v);
		}
	}
}
int n,m,u,v,w,i;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	cin >> a >> b >> c >> d;
	forr (i,1,m){
		cin >> u >> v >> w;
		g[u].pb({v,w});
		g[v].pb({u,w});
	}
	calc(a,0);
	calc(b,1);
	calc(c,2);
	calc(d,3);
	forr (i,1,n){
		//cout << i << " " << dis[0][i] << "\n";
		for (pii v : g[i])
			if (dis[0][v.st] + v.nd + dis[1][i] == mn)
				ng[v.st].pb(i),deg[i]++;
		dp[0][i] = dis[2][i];
		dp[1][i] = dis[3][i];
	}
	finalcalc();
	cout << min(ans,dis[2][d]);
	return 0;
}
/*



*/

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