Submission #1087358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087358		quangminh412	Commuter Pass (JOI18_commuter_pass)	C++14	55 / 100	156 ms	20624 KiB

commuter_pass

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

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const ll oo = 1e18;
const int maxn = 1e5 + 9;

struct Near
{
	int tar, id;
	ll w;
	
	Near(int tar, int id, ll w) : tar(tar), id(id), w(w) {}
};

vector<Near> adj[maxn];
int state[2 * maxn];
vector<vector<ll>> floyd(500, vector<ll>(500, oo));
int n, m, s, t, u, v;

void dijkstra2(int s)
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<ll> dist(n + 2, oo);
	pq.push({dist[s] = 0, s});
	
	while (!pq.empty())
	{
		int u = pq.top().second;
		ll w = pq.top().first;
		pq.pop();
		
		if (dist[u] != w) continue;
		
		for (Near nxt : adj[u])
		{
			int v = nxt.tar;
			int id = nxt.id;
			ll ww = nxt.w;
			
			if (dist[v] > dist[u] + (state[id] == 1 ? 0 : ww))
				pq.push({dist[v] = dist[u] + (state[id] == 1 ? 0 : ww), v});		
		}
	}
	
	cout << dist[v] << '\n';
}

void dijkstra1(int s)
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<pair<int, int>> prev(n + 2, {0, 0});
	vector<ll> dist(n + 2, oo);
	pq.push({dist[s] = 0, s});
	
	while (!pq.empty())
	{
		int u = pq.top().second;
		ll w = pq.top().first;
		pq.pop();
		
		if (dist[u] != w) continue;
		
		for (Near nxt : adj[u])
		{
			int v = nxt.tar;
			ll ww = nxt.w;
			int id = nxt.id;
			
			if (dist[v] > dist[u] + ww)
			{
				prev[v] = {u, id};
				pq.push({dist[v] = dist[u] + ww, v});
			}
		}
	}
	
	while (t != s)
	{
		state[prev[t].second] = 1;
		t = prev[t].first;
	}
}

vector<ll> shortestPath(int s)
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	vector<ll> dist(n + 5, oo);
	pq.push({dist[s] = 0, s});
	
	while (!pq.empty())
	{
		int u = pq.top().second;
		ll w = pq.top().first;
		pq.pop();
		
		if (dist[u] != w) continue;
		
		for (Near nxt : adj[u])
		{
			int v = nxt.tar;
			ll ww = nxt.w;
			
			if (dist[v] > dist[u] + ww)
				pq.push({dist[v] = dist[u] + ww, v});
		}
	}
	
	return dist;
}

void solve_1()
{
	vector<ll> froms = shortestPath(s), fromt = shortestPath(t), fromv = shortestPath(v);
	
	ll ans = froms[v];
	for (int vertex = 1; vertex <= n; vertex++)
		if (froms[vertex] + fromt[vertex] == froms[t])
			ans = min(ans, fromv[vertex]);
	cout << ans << '\n';
}

void solve_3()
{
	for (int i = 1; i <= n; i++) floyd[i][i] = 0;
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				floyd[i][j] = min(floyd[i][j], floyd[i][k] + floyd[k][j]);
	
	ll ans = floyd[u][v];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (floyd[s][i] + floyd[i][j] + floyd[j][t] == floyd[s][t])
				ans = min({ans, floyd[u][i] + floyd[j][v], floyd[v][i] + floyd[j][u]});
	cout << ans << '\n';
}

signed main()
{
	if (fopen("test.inp", "r"))
	{
		freopen("test.inp", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	faster();

	cin >> n >> m >> s >> t >> u >> v;
	for (int i = 0; i < m; i++)
	{
		int u, v; cin >> u >> v;
		ll w; cin >> w;
		adj[u].emplace_back(v, i, w);
		adj[v].emplace_back(u, i, w);
		if (n <= 300) floyd[u][v] = floyd[v][u] = min(floyd[u][v], w);
	}
	
	if (s == u)
	{
		solve_1();
		return 0;
	}
	if (n <= 300)
	{
		solve_3();
		return 0;
	}
	dijkstra1(s);
	dijkstra2(u);

	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:152:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   freopen("test.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:153:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |   freopen("test.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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