제출 #908972

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

commuter_pass

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 10;
const ll mod = 998244353;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll n, m, from, to, fir, sec;
ll d[N], dp[N], used[N];
vector <pll> q[N];
void dfs(int v){
	used[v] = true;
	for(auto u : q[v]){
		if(d[u.F] + u.S == d[v]) dfs(u.F);
	}
}

ll d1[N][2];
void create(){
	d[from] = 0;
  	dp[from] = 1;
  	set <pll> st;
  	st.insert({d[from], from});
  	while((ll)st.size() != 0){
  		auto [place, v] = *st.begin();
  		st.erase(st.begin());
  		if(d[v] != place) continue;
  		
  		for(auto u : q[v]){
  			if(d[u.F] == d[v] + u.S){
  				dp[u.F] += dp[v];
  				dp[u.F] = min(1000LL, dp[u.F]);
  			}
  			if(d[u.F] == -1 || d[u.F] > d[v] + u.S){
  				d[u.F] = d[v] + u.S;
  				dp[u.F] = dp[v];
  				st.insert({d[u.F], u.F});
  			}
  		}
  	}
}
set <pair <pll, pll>> st;
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	//freopen("bank.in", "r", stdin);
  	//freopen("bank.out", "w", stdout);
  	cin >> n >> m >> from >> to >> fir >> sec;
  	for(ll i = 0, a, b, c; i < m; i++){
  		cin >> a >> b >> c;
  		q[a].pb({b, c});
  		q[b].pb({a, c});
  	}
  	for(ll i = 1; i <= n; i++){
  		d[i] = -1;
  		d1[i][0] = d1[i][1] = -1;
  	}
  	create();
  	dfs(to);
  	d1[fir][0] = 0;
  	st.insert({{0, fir}, {0, 0}});
  	if(used[fir]){
  		d1[fir][1] = 0;
  		st.insert({{0, fir}, {1, 1}});
  		st.insert({{0, fir}, {1, -1}});
  	}
  	
  	while((ll)st.size() != 0){
  		auto [f, s] = *st.begin();
  		auto [place, v] = f;
  		auto [was, dir] = s;
  		st.erase(st.begin());
  		if(place != d1[v][was]) continue;
  		//cout << place << " "<< v << " "<< was << " "<< dir << endl;
  		for(auto u : q[v]){
  			if(dir != 0){
  				//cout << d[v] << " "<< dir * u.S << " "<< d[u.F] << endl;
  				if(used[u.F] && d[v] + dir * u.S == d[u.F]){
  					if(d1[v][1] < d1[u.F][1] || d1[u.F][1] == -1){
  						d1[u.F][1] = d1[v][1];
  						st.insert({{d1[u.F][1], u.F}, {1, dir}});
  					}
  				}
  			} else{
  				if(was == 0 && used[u.F]){
  					if(d1[v][0] + u.S < d1[u.F][1] || d1[u.F][1] == -1){
						d1[u.F][1] = d1[v][0] + u.S;
						st.insert({{d1[u.F][1], u.F}, {1, -1}});
						st.insert({{d1[u.F][1], u.F}, {1, 1}});
					}
  				}
  			}
  			if(d1[v][was] + u.S < d1[u.F][was] || d1[u.F][was] == -1){
				d1[u.F][was] = d1[v][was] + u.S;
				st.insert({{d1[u.F][was], u.F}, {was, 0}});
			}
  		}
  	}
  	cout << min(d1[sec][0], d1[sec][1]);
  return 0;
}

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