Submission #153577

#	Time	Username	Problem	Language	Result	Execution time	Memory
153577		mhy908	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	437 ms	25760 KiB

commuter_pass

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int n, m;
int u, v, s, t;
vector<vector<pii > > adj;
vector<vector<int> > adj2;
vector<LL> udis, vdis, dis, mini1, mini2;
priority_queue<pair<LL, int> > pq;
vector<int> pre;
vector<bool> vis;
stack<int> topo;

void dfs(int index) {
	if (vis[index]) return;
	vis[index] = true;
	for (int i = 0; i < adj[index].size(); i++) {
		int x = adj[index][i].first;
		int d = adj[index][i].second;
		if (dis[index] - d == dis[x]) {
			adj2[index].push_back(x);
			dfs(x);
		}
	}
	topo.push(index);
}

int main() {
	scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
	s--;t--;u--;v--;
	int i1, i2, i3;
	adj.resize(n);
	adj2.resize(n);
	udis.resize(n, llinf);
	vdis.resize(n, llinf);
	dis.resize(n, llinf);
	mini1.resize(n, llinf);
	mini2.resize(n, llinf);
	vis.resize(n);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &i1, &i2, &i3);
		i1--; i2--;
		adj[i1].emplace_back(i2, i3);
		adj[i2].emplace_back(i1, i3);
	}
	udis[u] = 0;
	pq.push(make_pair(0, u));
	while (!pq.empty()) {
		int x = pq.top().second;
		long long d = -pq.top().first;
		pq.pop();
		if (udis[x] != d) continue;
		for (int i = 0; i < adj[x].size(); i++) {
			int y = adj[x][i].first;
			int w = adj[x][i].second;
			if (udis[y] > d + w) {
				udis[y] = d + w;
				pq.push(make_pair(-d-w, y));
			}
		}
	}
	vdis[v] = 0;
	pq.push(make_pair(0, v));
	while (!pq.empty()) {
		int x = pq.top().second;
		LL d = -pq.top().first;
		pq.pop();
		if (vdis[x] != d) continue;
		for (int i = 0; i < adj[x].size(); i++) {
			int y = adj[x][i].first;
			int w = adj[x][i].second;
			if (vdis[y] > d + w) {
				vdis[y] = d + w;
				pq.push(make_pair(-d-w, y));
			}
		}
	}
	dis[s] = 0;
	pq.push(make_pair(0, s));
	while (!pq.empty()) {
		int x = pq.top().second;
		LL d = -pq.top().first;
		pq.pop();
		if (dis[x] != d) continue;
		for (int i = 0; i < adj[x].size(); i++) {
			int y = adj[x][i].first;
			int w = adj[x][i].second;
			if (dis[y] > d + w) {
				dis[y] = d + w;
				pq.push(make_pair(-d-w, y));
			}
		}
	}
	dfs(t);
	LL ans = udis[v];
	while (!topo.empty()) {
		int x = topo.top();
		topo.pop();
		mini1[x] = min(mini1[x], udis[x]);
		mini2[x] = min(mini2[x], vdis[x]);
		ans = min(ans, vdis[x] + mini1[x]);
		ans = min(ans, udis[x] + mini2[x]);
		for (int i = 0; i < adj2[x].size(); i++) {
			int y = adj2[x][i];
			mini1[y] = min(mini1[y], mini1[x]);
			mini2[y] = min(mini2[y], mini2[x]);
		}
	}
	printf("%lld", ans);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[index].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
commuter_pass.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
commuter_pass.cpp:93:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
commuter_pass.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj2[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d", &n, &m, &s, &t, &u, &v);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &i1, &i2, &i3);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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