Submission #142558

#	Time	Username	Problem	Language	Result	Execution time	Memory
142558		DrumpfTheGodEmperor	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	961 ms	48548 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5;
struct DPState {
	int stCost = infll, uvCost = infll;
	DPState(int stCost = infll, int uvCost = infll): stCost(stCost), uvCost(uvCost) {};
	bool operator<(const DPState &rhs) const {
		if (stCost == rhs.stCost) return uvCost < rhs.uvCost;
		return stCost < rhs.stCost;
	}
	bool operator!=(const DPState &rhs) const {
		if (stCost != rhs.stCost || uvCost != rhs.uvCost) return true;
		return false;
	}
} dp[N][3];
typedef pair<DPState, ii> iii;
int n, m, s, t, u, v, ans;
vector<ii> g[N];
int distu[N], distv[N];
void djisktra(int src, int (&dist)[N]) {
	memset(dist, 63, sizeof dist);
	dist[src] = 0;
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push(ii(0, src));
	while (!pq.empty()) {
		ii tmp = pq.top(); pq.pop();
		int vertex = tmp.se, cost = tmp.fi;
		if (dist[vertex] != cost) continue;
		fa (i, g[vertex]) {
			int dest = i.fi, edgeCost = i.se;
			if (cost + edgeCost < dist[dest]) {
				dist[dest] = cost + edgeCost;
				pq.push(ii(dist[dest], dest));
			}
		}
	}
}
void solve() {
	fw (i, 0, n) fw (j, 0, 3) dp[i][j] = DPState();
	djisktra(u, distu);
	djisktra(v, distv);
	priority_queue<iii, vector<iii>, greater<iii>> pq;
	pq.push(iii(DPState(0, 0), ii(s, 0)));
	dp[s][0] = DPState(0, 0);
	while (!pq.empty()) {
		iii tmp = pq.top(); pq.pop();
		int state = tmp.se.se, vertex = tmp.se.fi;
		DPState cost = tmp.fi;
		if (cost != dp[vertex][state]) continue; 
		//Change vertexes or change state
		//Change vertex:
		fa (i, g[vertex]) {
			int dest = i.fi, edgeCost = i.se;
			if (DPState(cost.stCost + edgeCost, cost.uvCost) < dp[dest][state]) {
				dp[dest][state] = DPState(cost.stCost + edgeCost, cost.uvCost);
				pq.push(iii(dp[dest][state], ii(dest, state)));
			}
		}
		//Change state
		if (state == 0) {
			if (DPState(cost.stCost, cost.uvCost + distu[vertex]) < dp[vertex][1]) {
				dp[vertex][1] = DPState(cost.stCost, cost.uvCost + distu[vertex]);
				pq.push(iii(dp[vertex][1], ii(vertex, 1)));
			}
		} else if (state == 1) {
			if (DPState(cost.stCost, cost.uvCost + distv[vertex]) < dp[vertex][2]) {
				dp[vertex][2] = DPState(cost.stCost, cost.uvCost + distv[vertex]);
				pq.push(iii(dp[vertex][2], ii(vertex, 2)));
			}
		}
	}
	ans = min(ans, dp[t][2].uvCost);
	ans = min(ans, distu[v]);
//	fw (i, 0, n) fw (j, 0, 3) cout << "dp[" << i << "][" << j << "] = " << dp[i][j].stCost << " " << dp[i][j].uvCost << "\n";
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> s >> t >> u >> v;
	s--, t--, u--, v--;
	fw (i, 0, m) {
		int v1, v2, cost;
		cin >> v1 >> v2 >> cost;
		v1--, v2--;
		g[v1].pb(ii(v2, cost));
		g[v2].pb(ii(v1, cost));
	}
	ans = infll;
	solve();
	//Swap u v and do the same thing
	swap(u, v);
	solve();
	cout << ans;
	return 0;
}

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