Submission #253888

#	Time	Username	Problem	Language	Result	Execution time	Memory
253888		ChrisT	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	440 ms	19492 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pli = pair<long long, int>;
using ll = long long;
const int MN = 1e5 + 5;
vector<pii> adj[MN];
ll distU[MN], distV[MN], distS[MN], distT[MN], dpU[MN], dpV[MN];
int deg[MN];
void dijkstra (int source, long long *dist) {
	priority_queue<pli,vector<pli>,greater<pli>> pq;
	dist[source] = 0; pq.push({0,source});
	while (!pq.empty()) {
		ll d = pq.top().first; int cur = pq.top().second; pq.pop();
		if (d > dist[cur]) continue;
		for (pii &p : adj[cur]) if (d + p.second < dist[p.first]) {
			dist[p.first] = d + p.second;
			pq.push({dist[p.first],p.first});
		}
	}
}
int main () { //yikes
	int n,m,s,t,u,v;
	scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
	while (m--) {
		int a,b,c;
		scanf ("%d %d %d",&a,&b,&c);
		adj[a].emplace_back(b,c);
		adj[b].emplace_back(a,c);
	}
	memset(distU,0x3f,sizeof distU); memset(distV,0x3f,sizeof distV); memset(distS,0x3f,sizeof distS); memset(distT,0x3f,sizeof distT);
	dijkstra(u,distU); dijkstra(v,distV); dijkstra(s,distS); dijkstra(t,distT);
	for (int i = 1; i <= n; i++) {
		dpU[i] = distU[i]; dpV[i] = distV[i];
		if (distS[i] + distT[i] == distS[t]) {
			for (pii p : adj[i]) if (distS[i] + p.second == distS[p.first] && distS[p.first] + distT[p.first] == distS[t]) ++deg[p.first];
		}
	}
	queue<int> q; q.push(s);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (pii p : adj[cur]) if (distS[cur] + p.second == distS[p.first] && distS[p.first] + distT[p.first] == distS[t]) {
			dpU[p.first] = min(dpU[p.first],dpU[cur]); dpV[p.first] = min(dpV[p.first],dpV[cur]);
			if (!(--deg[p.first])) q.push(p.first);
		} 
	}
	ll ret = LLONG_MAX;
	for (int i = 1; i <= n; i++) {
		ret = min({ret,dpU[i]+distV[i],dpV[i]+distU[i]});
	}
	printf ("%lld\n",ret);
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&a,&b,&c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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