Submission #116948

#	Time	Username	Problem	Language	Result	Execution time	Memory
116948		roseanne_pcy	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	524 ms	22056 KiB

commuter_pass

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

vector< ii > adj[maxn];
int n, m;
int s, t, U, V;

ll udist[maxn];
ll vdist[maxn];
ll tdist[maxn];
ll sdist[maxn];

ll udp[maxn];
ll vdp[maxn];

void dijk(int S, ll *dist)
{
	for(int i = 1; i<= n; i++) dist[i] = 4e18;
	dist[S] = 0; 
	priority_queue< pair<ll, int> > pq;
	pq.push({0, S});
	while(!pq.empty())
	{
		auto x = pq.top(); pq.pop();
		int u = x.Y, d = -x.X;
		if(d> dist[u]) continue; 
		for(auto kk : adj[u])
		{
			int v = kk.X, w = kk.Y;
			if(dist[v]> dist[u]+w)
			{
				dist[v] = dist[u]+w;
				pq.push({-dist[v], v});	
			}
		}
	}
}

vector<int> buck[maxn];

bool cmp(int a, int b)
{
	return tdist[a]< tdist[b];
}

int main()
{
	scanf("%d %d", &n, &m);
	scanf("%d %d %d %d", &s, &t, &U, &V);
	for(int i = 1; i<= m; i++)
	{
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		adj[u].pb(ii(v, w));
		adj[v].pb(ii(u, w));
	}
	dijk(U, udist); dijk(V, vdist);
	dijk(t, tdist); dijk(s, sdist);
	vector<int> vec;
	for(int i = 1; i<= n; i++) if(i != t) vec.pb(i);
	sort(vec.begin(), vec.end(), cmp);
	udp[t] = udist[t];
	vdp[t] = vdist[t];
	ll best = udist[V];
	for(int u : vec)
	{
		udp[u] = udist[u];
		vdp[u] = vdist[u];
		for(auto kk : adj[u])
		{
			int v = kk.X, w = kk.Y;
			if(tdist[u] == tdist[v]+w)
			{
				udp[u] = min(udp[u], udp[v]);
				vdp[u] = min(vdp[u], vdp[v]);
			}
		}
		if(sdist[u] + tdist[u] != sdist[t]) continue;
		best = min(best, udp[u]+vdist[u]);
		best = min(best, vdp[u]+udist[u]);
	}
	printf("%lld\n", best);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &s, &t, &U, &V);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:61:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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