Submission #305359

#	Time	Username	Problem	Language	Result	Execution time	Memory
305359		ChrisGe123	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2100 ms	51220 KiB

commuter_pass

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

typedef long long ll;
#define maxn 100002
#define maxm 200002

int n, m, s, t, u, v;
vector<int> parents[maxn]; //the first one stores the parents using the dijkstras thing for source S, the second one stores with source T
vector<pair<int, ll> > adj[maxn]; //first one is the id, second one is the cost of the edge //max cost is one billion
ll dist[maxn][3]; //the first one stores the distances from source S, the second stores from Source U, the third one stores from Source V
vector<int> shortpathchildren[maxn];
vector<int> dagnodes;
bool vis[maxn];
ll dpU[maxn][2]; //dpU[i] gives the minimum distance from U to any vertex between i and S 
ll dpV[maxn][2]; //dpV[i] gives the minimum distance from V to any vertex between i and T 

ll dpUfuncone(int i)
{
	if (dpU[i][0] != LLONG_MAX)
	{
		return dpU[i][0];
	}
	if (i == s)
	{
		return dist[s][1];
	}
	ll temp = dist[i][1];
	for (auto j: parents[i])
	{
		temp = min(temp, dpUfuncone(j));
	}
	// if (temp < 0)
	// {
	// 	cerr << i << " " << temp << endl;
	// }
	return dpU[i][0] = temp;
}

ll dpVfuncone(int i)
{
	if (dpV[i][0] != LLONG_MAX)
	{
		return dpV[i][0];
	}
	if (i == t)
	{
		//cerr << "YES: " << dist[t][2] << endl;
		return dist[t][2];
	}
	ll temp = dist[i][2];
	for (auto j: shortpathchildren[i])
	{
		temp = min(temp, dpVfuncone(j));
	}
	return dpV[i][0] = temp;
}

ll dpUfunctwo(int i)
{
	if (dpU[i][1] != LLONG_MAX)
	{
		return dpU[i][1];
	}
	if (i == t)
	{
		return dist[t][1];
	}
	ll temp = dist[i][1];
	for (auto j: shortpathchildren[i])
	{
		temp = min(temp, dpUfunctwo(j));
	}
	return dpV[i][1] = temp;
}

ll dpVfunctwo(int i)
{
	if (dpU[i][1] != LLONG_MAX)
	{
		return dpU[i][0];
	}
	if (i == s)
	{
		return dist[s][2];
	}
	ll temp = dist[i][2];
	for (auto j: parents[i])
	{
		temp = min(temp, dpVfunctwo(j));
	}
	return dpV[i][1] = temp;
}
void dijkstras(int source, int use)
{
	priority_queue<pair<int, ll>, vector<pair<int, ll> >, greater<pair<int, ll> > > points; //first one is the id, second is the distance from source
	for (int i=0; i<n; i++)
	{
		dist[i][use] = LLONG_MAX;
	}
	dist[source][use] = 0;
	points.push(make_pair(source, 0));
	while (points.size())
	{
		pair<int, ll> temp = points.top();
		points.pop();
		ll cdist = temp.second;
		int id = temp.first;
		// if (use == 2)
		// {
		// 	cerr << id << " " << cdist << endl;
		// 	// if (id == 2)
		// 	// {
		// 	// 	cerr << cdist << endl; //for some reason this becomes -1294967296
		// 	// 	cerr << dist[id][use] << endl;
		// 	// }
		// }
		if (cdist != dist[id][use])
		{
			continue;
		}
		for (auto k: adj[id])
		{
			// if (use == 2)
			// {
			// 	cerr << id << ": " << k.first << endl;
			// 	// cerr << dist[k.first][use] << endl;
			// 	// cerr << cdist + k.second << endl;
			// 	// cerr << endl;
			// }
			if (dist[k.first][use] > cdist + k.second)
			{
				// if (use == 2)
				// {
				// 	cerr << id << ": " << k.first << endl;
				// 	// cerr << dist[k.first][use] << endl;
				// 	// cerr << cdist + k.second << endl;
				// 	// cerr << endl;
				// }
				dist[k.first][use] = cdist + k.second;
				if (use == 0)
				{
					parents[k.first].clear();
					parents[k.first].push_back(id);
				}
				// if (use == 2 && k.first == 2)
				// {
				// 	cerr << dist[k.first][use] << endl; //this is still 3000000000
				// }
				points.push(make_pair(k.first, dist[k.first][use]));
			}
			else if (use == 0 && dist[k.first][use] == cdist + k.second)
			{
				parents[k.first].push_back(id);
				//we won't push this back into the queue because if the thing is not infinity, that the last time that it was reduced
				// it was already pushed into the priority queue, meaning that another update with still the same distance is meaningless
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("joi.in", "r", stdin);
	//freopen("joi.out", "w", stdout);
	cin >> n >> m >> s >> t >> u >> v;
	s--;
	t--;
	u--;
	v--;
	for (int i=0; i<m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		adj[a].push_back(make_pair(b,c));
		adj[b].push_back(make_pair(a,c));
	}

	//let's first see that we've read everything in correctly
	dijkstras(s, 0);
	//then check that we're doing the dijkstras correctly from source s
	dijkstras(u, 1);
	dijkstras(v, 2);
	//cerr << dist[t][2] << endl;
	//then check that we're getting the right dijkstras from u and v
	//we should probably assemble the lowest path tree
	queue<int> stuff;
	stuff.push(t);
	vis[t] = true;
	dagnodes.push_back(t);
	while (stuff.size())
	{
		int cur = stuff.front();
		stuff.pop();
		for (int i=0; i<parents[cur].size(); i++)
		{
			int k = parents[cur][i];
			shortpathchildren[k].push_back(cur);
			if (!vis[k])
			{
				dagnodes.push_back(k);
				stuff.push(k);
				vis[k] = true;
			}
		}
	}
	//then we should check that the dagnodes and children are correct
	for (auto k: dagnodes)
	{
		dpU[k][0] = LLONG_MAX;
		dpV[k][0] = LLONG_MAX;
	}
	ll minlengthone = LLONG_MAX;
	for (auto k: dagnodes)
	{
		// ll x = dpUfuncone(k);
		// ll y = dpVfuncone(k);
		// cerr << "from node " << k << ", we get " << x << " " << y << endl;
		minlengthone = min(minlengthone, dpUfuncone(k) + dpVfuncone(k));
		// if (dpUfuncone(k) + dpVfuncone(k) < 0)
		// {
		// 	cerr << k << endl;
		// }
	}
	//then we check the dp process

	for (auto k: dagnodes)
	{
		dpU[k][1] = LLONG_MAX;
		dpV[k][1] = LLONG_MAX;
	}
	ll minlengthtwo = LLONG_MAX;
	for (auto k: dagnodes)
	{
		minlengthtwo = min(minlengthtwo, dpUfunctwo(k) + dpVfunctwo(k));
	}

	//then we check the second dp process
	// cerr << dist[u][2] << endl;
	// cerr << minlengthone << endl;
	// cerr << minlengthtwo << endl;
	// cerr << LLONG_MIN << endl;
	//how did both become LL_ONG_MIN? this must mean that dpUfunc and dpVfunc returned LLONG_MIN, but what?
	cout << min(dist[u][2], min(minlengthone, minlengthtwo)) << endl;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |   for (int i=0; i<parents[cur].size(); i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~

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