제출 #1074639

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

commuter_pass

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

typedef long long ll;
typedef pair<int, int> pii;

#define sep ' '
#define fastIO 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
const int N = 1e5+100;
const ll LLINF = 2e18;
int n, m, s, t, X, Y;
struct edge {
	int w, st, fn;
	edge() {
		w = st = fn = 1;
	}
};
edge Edge(int u, int v, int w) {
	edge e;
	e.st = u, e.fn = v, e.w = w;
	return e;
}

struct cmp {
    bool operator()(const pair<long long, edge>& lhs, const pair<long long, edge>& rhs) const {
        if (lhs.first != rhs.first) return lhs.first < rhs.first;
        if (lhs.S.w != rhs.S.w) return lhs.S.w < rhs.S.w;
        if (lhs.S.st != rhs.S.st) return lhs.S.st < rhs.S.st;
        return lhs.S.fn < rhs.S.fn;
    }
};

vector<edge> adj[N], adj2[N], adj3[N], g1[N], g2[N];
ll dis[N];
int cnt = 10;
void dfs1(int v) {
	for(edge e: adj2[v]) {
		dfs1(e.fn);
		e.w = 0;
		g1[e.st].push_back(e);
		swap(e.st, e.fn);
		g2[e.st].push_back(e);
	}
}

signed main() {
	fastIO;
	cin >> n >> m;
	cin >> s >> t;
	cin >> X >> Y;
	s--, t--, X--, Y--;
	for(int i = 0 ; i < m ; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		adj[v].push_back(Edge(v, u, w));
		adj[u].push_back(Edge(u, v, w));
	}
	set<pair<ll, edge>, cmp> q;
	fill(dis, dis+n, LLINF);
	dis[s] = 0;
	for(edge e: adj[s])
		q.insert({e.w, e});
	while(q.size()) {
		auto [x, k] = *q.begin();
		q.erase(q.begin());
		if (dis[k.fn] != LLINF) {
			if (dis[k.fn] == x) adj2[k.fn].push_back(Edge(k.fn, k.st, k.w));
			continue;
		}
		dis[k.fn] = x;
		adj2[k.fn].push_back(Edge(k.fn, k.st, k.w));
		for(edge e: adj[k.fn])
			q.insert({0ll+x+e.w, e});
	}
	dfs1(t);
	for(int i = 0 ; i < n ; i ++) {
		adj3[i].clear();
		for(edge e: adj[i]) adj3[i].push_back(e);
		for(edge e: g1[i]) adj3[i].push_back(e);
	}
	fill(dis, dis+n, LLINF);
	dis[X] = 0;
	for(edge e: adj3[X])
		q.insert({e.w, e});
	while(q.size()) {
		auto [x, k] = *q.begin();
		q.erase(q.begin());
		if (dis[k.fn] != LLINF) continue;
		dis[k.fn] = x;
		for(edge e: adj3[k.fn])
			q.insert({0ll+x+e.w, e});
	}
	long long ans = dis[Y];
	for(int i = 0 ; i < n ; i ++) {
		adj3[i].clear();
		for(edge e: adj[i]) adj3[i].push_back(e);
		for(edge e: g2[i]) adj3[i].push_back(e);
	}
	fill(dis, dis+n, LLINF);
	dis[X] = 0;
	for(edge e: adj3[X])
		q.insert({e.w, e});
	while(q.size()) {
		auto [x, k] = *q.begin();
		q.erase(q.begin());
		if (dis[k.fn] != LLINF) continue;
		dis[k.fn] = x;
		for(edge e: adj3[k.fn])
			q.insert({0ll+x+e.w, e});
	}
	ans = min(ans, dis[Y]);
	cout << ans << endl;
	return 0;
}

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