Submission #719982

#	Time	Username	Problem	Language	Result	Execution time	Memory
719982		yellowtoad	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	320 ms	35392 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#define f first
#define se second
#define int long long
#define pll pair<long long,long long>
using namespace std;

long long n, m, s, t, ss, tt, dist[100010], disu[100010], disv[100010], vis[100010], in[100010], minu[100010], minv[100010], minn[100010];
vector<pll> edge[100010];
vector<long long> dag[100010];
priority_queue<pll,vector<pll>,greater<pll>> pq;

void dijk(int st, long long (&dis)[100010]) {
	pq.push({0,st});
	for (int i = 1; i <= n; i++) dis[i] = 1e18, vis[i] = 0;
	dis[st] = 0;
	while (pq.size()) {
		long long u = pq.top().se;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = 0; i < edge[u].size(); i++) {
			if (dis[edge[u][i].f] > dis[u]+edge[u][i].se) {
				dis[edge[u][i].f] = dis[u]+edge[u][i].se;
				pq.push({dis[edge[u][i].f],edge[u][i].f});
			}
		}
	}
}

void dfs(int u) {
	minu[u] = min(minu[u],disu[u]);
	minv[u] = min(minv[u],disv[u]);
	minn[u] = min(minn[u],min(minu[u]+disv[u],minv[u]+disu[u]));
	for (int i = 0; i < dag[u].size(); i++) {
		long long v = dag[u][i];
		in[v]--;
		minu[v] = min(minu[v],minu[u]);
		minv[v] = min(minv[v],minv[u]);
		minn[v] = min(minn[v],minn[u]);
		if (!in[v]) dfs(v);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> s >> t >> ss >> tt;
	for (int i = 1; i <= m; i++) {
		long long u, v, w;
		cin >> u >> v >> w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dijk(ss,disu);
	dijk(tt,disv);
	dijk(s,dist);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < edge[i].size(); j++) {
			if (dist[i]+edge[i][j].se == dist[edge[i][j].f]) {
				dag[i].push_back(edge[i][j].f);
				in[edge[i][j].f]++;
			}
		}
	}
	for (int i = 1; i <= n; i++) minu[i] = minv[i] = minn[i] = 1e18;
	dfs(s);
	cout << min(disu[tt],minn[t]) << endl;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(long long int, long long int (&)[100010])':
commuter_pass.cpp:24:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int i = 0; i < edge[u].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int)':
commuter_pass.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0; i < dag[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j = 0; j < edge[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~

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