Submission #292500

#	Time	Username	Problem	Language	Result	Execution time	Memory
292500		maomao90	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	1460 ms	33520 KiB

commuter_pass

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

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

#define INF 1000000000000000000

int n, m;
int s, t;
int u, v;
vector <ii> adjList[200005], adjList1[200005], adjList2[200005];
long long distu[100005], distv[100005], dists[100005], distt[100005];
long long ans;

priority_queue<ll, vector<ii>, greater<ii> > pq;
void dijkstra(int a, long long *dist) {
	for (int i = 1; i <= n; i++) dist[i] = INF;
	dist[a] = 0;
	pq.emplace(0, a);
	while (!pq.empty()) {
		int u, d; tie(d, u) = pq.top(); pq.pop();
		if (d > dist[u]) continue;
		for (ii vw : adjList[u]) {
			int v, w; tie(v, w) = vw;
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.emplace(dist[v], v);
			}
		}
	}
}

long long memo[100005][2];
long long dp(int i, bool stt) {
	if (memo[i][stt] != -1) return memo[i][stt];
	if (i == v) return 0;
	memo[i][stt] = INF;
	for (ii vw : adjList[i]) {
		int v, w; tie(v, w) = vw;
		if ((stt && dists[i] + distt[v] + w == dists[t]) || (!stt && dists[v] + distt[i] + w == dists[t]))
			memo[i][stt] = min(memo[i][stt], dp(v, stt));
		else memo[i][stt] = min(memo[i][stt], distv[v] + w);
	}
	return memo[i][stt];
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d", &s, &t);
	scanf("%d%d", &u, &v);
	for (int i = 0; i < m; i++) {
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		adjList[a].emplace_back(b, c);
		adjList[b].emplace_back(a, c);
	}
	dijkstra(u, distu);
	dijkstra(v, distv);
	dijkstra(s, dists);
	dijkstra(t, distt);
	ans = distu[v];
	memset(memo, -1, sizeof memo);
	for (int i = 1; i <= n; i++) {
		if (dists[i] + distt[i] == dists[t]) {
			ans = min(ans, distu[i] + min(dp(i, true), dp(i, false)));
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  scanf("%d%d", &s, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d%d", &u, &v);
      |  ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:53:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   int a, b, c; scanf("%d%d%d", &a, &b, &c);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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