제출 #61852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61852		kingpig9	Commuter Pass (JOI18_commuter_pass)	C++11	100 / 100	982 ms	83172 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, int> edge;
const int MAXN = 100010;
const ll INF = 0x0101010101010101;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void setmin (ll &a, ll b) {
	if (a > b) {
		a = b;
	}
}

int N, M, S, T, U, V;
vector<edge> adj[MAXN];
ll sdist[MAXN], tdist[MAXN], udist[MAXN], vdist[MAXN];
bool vis[MAXN];

void dijkstra (ll *dist, int s) {
	fill_n(dist + 1, N, INF);
	fill_n(vis + 1, N, false);
	dist[s] = 0;
	priority_queue<edge, vector<edge>, greater<edge>> pq;
	pq.emplace(0ll, s);

	while (!pq.empty()) {
		int u = pq.top().se;
		ll w = pq.top().fi;
		pq.pop();

		if (vis[u]) {
			continue;
		}
		vis[u] = true;

		for (edge e : adj[u]) {
			ll nw = w + e.fi;
			int v = e.se;
			if (nw < dist[v]) {
				dist[v] = nw;
				pq.emplace(nw, v);
			}
		}
	}
}

ll dp[MAXN];
vector<int> dag[MAXN];

ll getdp (int x) {
	ll &ref = dp[x];
	if (ref != INF) {
		return ref;
	}
	ref = vdist[x];

	for (int y : dag[x]) {
		setmin(ref, getdp(y));
	}
	return ref;
}

ll go() {
	debug("---------PROPAGANDA--------\n");
#warning reset EVERYTHING!
	dijkstra(sdist, S);
	dijkstra(tdist, T);
	dijkstra(udist, U);
	dijkstra(vdist, V);

	//now start the work - calc SP dag
	//U -> vertex -> somewhere in sub of vertex -> V
	fillchar(dp, 1);

	for (int i = 1; i <= N; i++) {
		dag[i].clear();
		for (edge e : adj[i]) {
			int j = e.se;
			//S -> i -> j -> T
			if (sdist[i] + e.fi + tdist[j] == sdist[T]) {
				debug("%d -> %d\n", i, j);
				dag[i].push_back(j);
			}
		}
	}

	ll ans = udist[V];
	for (int i = 1; i <= N; i++) {
		setmin(ans, udist[i] + getdp(i));
	}
	return ans;
}

int main() {
	scanf("%d %d %d %d %d %d", &N, &M, &S, &T, &U, &V);
	for (int i = 1; i <= M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		adj[a].emplace_back(c, b);
		adj[b].emplace_back(c, a);
	}

	ll ans = INF;
	for (int qi = 0; qi < 2; qi++) {
		swap(U, V);
		setmin(ans, go());
	}
	printf("%lld\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp:73:2: warning: #warning reset EVERYTHING! [-Wcpp]
 #warning reset EVERYTHING!
  ^~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:103: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:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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