Submission #345035

#	Time	Username	Problem	Language	Result	Execution time	Memory
345035		wwdd	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	711 ms	38504 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pl> vpl;
typedef vector<vpl> al;
typedef vector<ll> vl;
typedef pair<pl,int> stt;
const ll INFL = 1e18;
al g[3];
void dja(int su, int sv) {
	int so[2] = {su,sv};
	vl dist[2];
	for(int idx=0;idx<2;idx++) {
		int bu = so[idx];
		dist[idx].assign(g[0].size(),INFL);
		priority_queue<pl,vpl, greater<pl>> pq;
		dist[idx][bu] = 0;
		pq.push({0,bu});
		while(!pq.empty()) {
			pl co = pq.top();pq.pop();
			ll u = co.second;
			if(co.first > dist[idx][u]) {continue;}
			for(int i=0;i<g[0][u].size();i++) {
				pl no = g[0][u][i];
				ll v = no.first;
				ll ko = no.second;
				if(dist[idx][v] > dist[idx][u]+ko) {
					dist[idx][v] = dist[idx][u]+ko;
					pq.push({dist[idx][v],v});
				}
			}
		}
	}
	ll mu = dist[1][su]+dist[0][su];
	for(int idx=0;idx<2;idx++) {
		for(int i=0;i<g[0].size();i++) {
			if(dist[1][i]+dist[0][i] != mu) {continue;}
			for(int j=0;j<g[0][i].size();j++) {
				pl no = g[0][i][j];
				ll v = no.first;
				ll ko = no.second;
				if(dist[idx][v]+ko == dist[idx][i]) {
					g[idx+1][i].push_back({v,0});
				}
			}
		}
	}
}
vl dist[4];
int main() {
	ll n,m;
	cin >> n >> m;
	ll so,to;
	cin >> so >> to;
	so--;to--;
	ll ru,rv;
	cin >> ru >> rv;
	ru--;rv--;
	g[0].assign(n,vpl());
	g[1].assign(n,vpl());
	g[2].assign(n,vpl());
	for(int i=0;i<m;i++) {
		ll a,b,c;
		cin >> a >> b >> c;
		a--;b--;
		g[0][a].push_back({b,c});
		g[0][b].push_back({a,c});
	}
	for(int i=0;i<4;i++) {
		dist[i].assign(n,INFL);
	}
	priority_queue<stt,vector<stt>,greater<stt> > pq;
	dja(so,to);
	pq.push({{0,ru},0});
	dist[0][ru] = 0;
	while(!pq.empty()) {
		stt cb = pq.top();pq.pop();
		pl co = cb.first;
		ll u = co.second;
		ll gid = cb.second;
		if(co.first > dist[gid][u]) {continue;}
		vpl& bob = g[gid%3][u];
		for(int i=0;i<bob.size();i++) {
			pl co = bob[i];
			ll v = co.first;
			ll di = co.second;
			if(dist[gid][v] > dist[gid][u]+di) {
				dist[gid][v] = dist[gid][u]+di;
				pq.push({{dist[gid][v],v},gid});
			}
		}
		if(gid == 0) {
			for(int i=1;i<=2;i++) {
				if(dist[i][u] > dist[0][u]) {
					dist[i][u] = dist[0][u];
					pq.push({{dist[i][u],u},i});
				}
			}
		} else if(gid < 3) {
			if(dist[3][u] > dist[gid][u]) {
				dist[3][u] = dist[gid][u];
				pq.push({{dist[3][u],u},3});
			}
		}
	}
	ll res = INFL;
	for(int i=0;i<4;i++) {
		res = min(res,dist[i][rv]);
	}
	cout << res << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dja(int, int)':
commuter_pass.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for(int i=0;i<g[0][u].size();i++) {
      |                ~^~~~~~~~~~~~~~~
commuter_pass.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0;i<g[0].size();i++) {
      |               ~^~~~~~~~~~~~
commuter_pass.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int j=0;j<g[0][i].size();j++) {
      |                ~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=0;i<bob.size();i++) {
      |               ~^~~~~~~~~~~

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