Submission #64292

#	Time	Username	Problem	Language	Result	Execution time	Memory
64292		keko37	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1769 ms	155808 KiB

commuter_pass

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>

using namespace std;

typedef long long llint;

const int MAXN = 100005;
const int MAXM = 200005;
const llint INF = 1000000000000000000LL;

llint n, m, s, t, uu, vv, sol = INF;
llint a[MAXM], b[MAXM], c[MAXM], dist[3*MAXN], bio[MAXN], ok[MAXM];
vector < pair <int, int> > v[MAXN], r[MAXN], p[MAXN];
set < pair <llint, llint> > st;

void obrni () {
	for (int i=1; i<=n; i++) {
		p[i].clear();
	}
	for (int i=1; i<=n; i++) {
		for (int j=0; j<r[i].size(); j++) {
			p[r[i] [j].first].push_back(make_pair(i, 0));
		}
	}
	for (int i=1; i<=n; i++) {
		r[i] = p[i];
	}
}

bool dfs (int x) {
	if (x == s) return 1;
	if (bio[x] != -1) return bio[x];
	bio[x] = 0;
	for (int i=0; i<r[x].size(); i++) {
		int sus = r[x] [i].first;
		int ind = r[x] [i].second;
		ok[ind] = dfs(sus);
		bio[x] |= ok[ind];
	}
	return bio[x];
}

void filter () {
	memset(bio, -1, sizeof bio);
	dfs(t);
	for (int i=1; i<=n; i++) {
		for (int j=0; j<r[i].size(); j++) {
			if (ok[r[i] [j].second]) p[i].push_back(r[i] [j]);
		}
	}
	for (int i=1; i<=n; i++) {
		r[i] = p[i];
	}
}

void dijkstra1 () {
	for (int i=1; i<=n; i++) {
		dist[i] = (i == s) ? 0LL : INF;
	}
	st.insert(make_pair(0, s));
	while (!st.empty()) {
		int cvor = st.begin() -> second;
		st.erase(st.begin());
		for (int i=0; i<v[cvor].size(); i++) {
			int sus = v[cvor] [i].first;
			int ind = v[cvor] [i].second;
			if (dist[cvor] + c[ind] < dist[sus]) {
				if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
				dist[sus] = dist[cvor] + c[ind];
				st.insert(make_pair(dist[sus], sus));
				r[sus].clear();
			}
			if (dist[cvor] + c[ind] == dist[sus]) r[sus].push_back(make_pair(cvor, ind));
		}
	}
}

void dijkstra2 () {
	for (int i=1; i<=n; i++) {
		for (int j=0; j<3; j++) {
			int cvor = i + j*MAXN;
			if (cvor == uu) dist[cvor] = 0; else dist[cvor] = INF;
		}
	}
	st.insert(make_pair(0, uu));
	while (!st.empty()) {
		int all = (st.begin() -> second);
		int tip = all / MAXN;
		int cvor = all % MAXN;
		st.erase(st.begin());
		for (int i=0; i<v[cvor].size(); i++) {
			int sus = v[cvor] [i].first;
			int ind = v[cvor] [i].second;
			if (tip == 1 || tip == 2) sus += 2*MAXN;
			if (dist[all] + c[ind] < dist[sus]) {
				if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
				dist[sus] = dist[all] + c[ind];
				st.insert(make_pair(dist[sus], sus));
			}
		}
		if (tip == 2) continue;
		for (int i=0; i<r[cvor].size(); i++) {
			int sus = r[cvor] [i].first + MAXN;
			if (dist[all] < dist[sus]) {
				if (dist[sus] != INF) st.erase(make_pair(dist[sus], sus));
				dist[sus] = dist[all];
				st.insert(make_pair(dist[sus], sus));
			}
		}
	}
	sol = min(sol, dist[vv]);
	sol = min(sol, dist[vv + MAXN]);
	sol = min(sol, dist[vv + MAXN*2]);
}

int main () {
	cin >> n >> m >> s >> t >> uu >> vv;
	for (int i=0; i<m; i++) {
		scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
		v[a[i]].push_back(make_pair(b[i], i));
		v[b[i]].push_back(make_pair(a[i], i));
	}
	dijkstra1();
	filter();
	dijkstra2();
	obrni();
	dijkstra2();
	cout << sol;
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void obrni()':
commuter_pass.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<r[i].size(); j++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'bool dfs(int)':
commuter_pass.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<r[x].size(); i++) {
                ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void filter()':
commuter_pass.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<r[i].size(); j++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra1()':
commuter_pass.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[cvor].size(); i++) {
                 ~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dijkstra2()':
commuter_pass.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[cvor].size(); i++) {
                 ~^~~~~~~~~~~~~~~
commuter_pass.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<r[cvor].size(); i++) {
                 ~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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