Submission #930049

#	Time	Username	Problem	Language	Result	Execution time	Memory
930049		jcelin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	686 ms	103508 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

ll dis[MAXN][4];
int n;
vii g[MAXN];
vi dag[MAXN], rv[MAXN], topo;
int indeg[MAXN];
bool ing[MAXN];

void dijkstra(int root, int id){
	for(int i=1; i<=n; i++) dis[i][id] = INF;
	dis[root][id] = 0;
	set<pll> s;
	for(int i=1; i<=n; i++) s.insert({dis[i][id], i});
	while(!s.empty()){
		ll d, u;
		tie(d, u) = *s.begin();
		s.erase(s.begin());
		for(auto &x : g[u]){
			int v = x.X;
			ll nd = d + x.Y;
			if(nd < dis[v][id]){
				s.erase({dis[v][id], v});
				dis[v][id] = nd;
				s.insert({dis[v][id], v});
			}
		}
	}
	
}

ll dp[MAXN], dp2[MAXN];

void solve(){
	int m;
	int s, t, u, v;
	cin >> n >> m >> s >> t >> u >> v;
	for(int i=0; i<m; i++){
		int a, b, w;
		cin >> a >> b >> w;
		g[a].PB({b, w});
		g[b].PB({a, w});
	}
	dijkstra(s, 0);
	dijkstra(t, 1);
	dijkstra(u, 2);
	dijkstra(v, 3);
	
	ll opt = INF, ans = INF;
	for(int i=1; i<=n; i++) opt = min(opt, dis[i][0] + dis[i][1]), ans = min(ans, dis[i][2] + dis[i][3]);
	for(int i=1; i<=n; i++) ing[i] = (dis[i][0] + dis[i][1] == opt);
	for(int i=1; i<=n; i++){
		for(auto &x : g[i]){
			if(dis[i][0] + x.Y + dis[x.X][1] == opt){
				dag[i].PB(x.X);
				rv[x.X].PB(i);
				indeg[x.X]++;
			}
		}
	}
	
	vi st;
	for(int i=1; i<=n; i++){
		if(!ing[i]) continue;
		if(indeg[i] == 0) st.PB(i);
	}
	
	
	while(st.size()){
		int cr = st.back();
		st.PPB();
		topo.PB(cr);
		for(auto &x : dag[cr]) if(--indeg[x] == 0) st.PB(x);
	}
	
	
	for(int i=1; i<=n; i++) dp[i] = dis[i][2], dp2[i] = dis[i][3];
	for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]);
	reverse(all(topo));
	for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]);
	reverse(all(topo));
	for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]);
	
	
	for(int i=1; i<=n; i++) dp[i] = dis[i][3], dp2[i] = dis[i][2];
	for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]);
	reverse(all(topo));
	for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]);
	reverse(all(topo));
	for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]);
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0; 
}

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