Submission #530836

#	Time	Username	Problem	Language	Result	Execution time	Memory
530836		Hanksburger	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	337 ms	34424 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
long long dist[3][100005], dp[3][100005], deg[100005], n, m, a, b, c, d, ans=1e18;
vector<pair<long long, long long> > adj[100005];
priority_queue<pair<long long, long long> > pq;
vector<long long> back[100005], front[100005];
bool visited[100005];
queue<long long> q;
void dijkstra(long long start)
{
	for (long long i=1; i<=n; i++)
	{
		visited[i]=0;
		dist[start][i]=1e18;
	}
	if (start==0)
	{
		dist[start][a]=0;
		pq.push({0, a});
	}
	else if (start==1)
	{
		dist[start][c]=0;
		pq.push({0, c});
	}
	else
	{
		dist[start][d]=0;
		pq.push({0, d});
	}
	while (!pq.empty())
	{
		long long u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (long long i=0; i<adj[u].size(); i++)
		{
			long long v=adj[u][i].first, w=adj[u][i].second;
			if (dist[start][u]+w<dist[start][v])
			{
				dist[start][v]=dist[start][u]+w;
				pq.push({-dist[start][v], v});
				if (!start)
				{
					back[v].clear();
					back[v].push_back(u);
				}
			}
			else if (!start && dist[start][u]+w==dist[start][v])
				back[v].push_back(u);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> a >> b >> c >> d;
	for (long long i=1; i<=m; i++)
	{
		long long u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dijkstra(0);
	dijkstra(1);
	dijkstra(2);
	for (long long i=1; i<=n; i++)
	{
//		cout << "dist of " << i << ": " << dist[0][i] << ' ' << dist[1][i] << ' ' << dist[2][i] << '\n';
		deg[i]=back[i].size();
		for (long long j=0; j<deg[i]; j++)
//		{
			front[back[i][j]].push_back(i);
//			cout << back[i][j] << " to " << i << " relationship" << '\n';
//		}
	}
	for (long long i=1; i<=n; i++)
		visited[i]=0;
	visited[a]=1;
	q.push(a);
	while (!q.empty())
	{
		long long u=q.front();
		q.pop();
		dp[0][u]=dist[1][u]+dist[2][u];
		dp[1][u]=dist[1][u];
		dp[2][u]=dist[2][u];
		for (long long i=0; i<back[u].size(); i++)
		{
			long long v=back[u][i];
			dp[0][u]=min(dp[0][u], dp[0][v]);
//			if (v==2)
//				cout << "traverse " << dp[0][v] << " from " << v << " to " << u << '\n';
			dp[1][u]=min(dp[1][u], dp[1][v]);
			dp[2][u]=min(dp[2][u], dp[2][v]);
		}
		dp[0][u]=min(dp[0][u], min(dp[1][u]+dist[2][u], dp[2][u]+dist[1][u]));
//		cout << "u " << u << ' ' << dp[1][u] << ' ' << dist[2][u] << ' ' << dp[2][u] << ' ' << dist[1][u] << ' ' << dp[0][u] << '\n';
		for (long long i=0; i<front[u].size(); i++)
		{
			long long v=front[u][i];
			if (!visited[v])
			{
				deg[v]--;
				if (!deg[v])
				{
					visited[v]=1;
					q.push(v);
				}
			}
		}
	}
	cout << min(dp[0][b], dist[1][d]);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(long long int)':
commuter_pass.cpp:38:24: 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]
   38 |   for (long long i=0; i<adj[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93:24: 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]
   93 |   for (long long i=0; i<back[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~~
commuter_pass.cpp:104:24: 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]
  104 |   for (long long i=0; i<front[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~~~

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