oj.uz

Submission #64291

# Submission time Handle Problem Language Result Execution time Memory
64291 2018-08-04T00:03:20 Z keko37 Commuter Pass (JOI18_commuter_pass) C++14
24 / 100
 2000 ms 54104 KB 
#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(dist[i], i));
	}
	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]) {
				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(dist[cvor], cvor));
		}
	}
	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]) {
				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]) {
				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

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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 46856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 54104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 54104 KB Output is correct
2 Correct 12 ms 54104 KB Output is correct
3 Correct 14 ms 54104 KB Output is correct
4 Correct 59 ms 54104 KB Output is correct
5 Correct 24 ms 54104 KB Output is correct
6 Correct 12 ms 54104 KB Output is correct
7 Correct 13 ms 54104 KB Output is correct
8 Correct 13 ms 54104 KB Output is correct
9 Correct 12 ms 54104 KB Output is correct
10 Correct 21 ms 54104 KB Output is correct
11 Correct 11 ms 54104 KB Output is correct
12 Correct 14 ms 54104 KB Output is correct
13 Correct 11 ms 54104 KB Output is correct
14 Correct 12 ms 54104 KB Output is correct
15 Correct 12 ms 54104 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 46856 KB Time limit exceeded
2 Halted 0 ms 0 KB -