Submission #170581

#	Time	Username	Problem	Language	Result	Execution time	Memory
170581		ZwariowanyMarcin	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	499 ms	18944 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 11;
const ll INF = 1e18;

int n, m, a, b, c;
int s, t;
int uu, vv;
vector <pair<int,int>> v[nax];
ll dis[3][nax];

priority_queue <pair<ll, int>> q;
bool odw[nax];

void dij(int pocz, int cnt) {
	for(int i = 1; i <= n; ++i) {
		dis[cnt][i] = INF;
		odw[i] = 0;
	}
	dis[cnt][pocz] = 0;
	q.push(mp(0, pocz));
	while(!q.empty()) {
		int ja = q.top().se;
		q.pop();
		if(odw[ja]) continue;
		odw[ja] = 1;
		for(auto it : v[ja]) {
			ll nowa = dis[cnt][ja] + it.se;
			if(nowa < dis[cnt][it.fi]) {
				dis[cnt][it.fi] = nowa;
				q.push(mp(-nowa, it.fi));
			}
		}
	}
}
	
ll ans = INF;
ll path[nax];
ll odl[nax];

void algo() {
	for(int i = 1; i <= n; ++i) {
		odw[i] = 0;
		odl[i] = INF;
		path[i] = INF;
	}
	q.push(mp(0, t));
	odl[t] = 0;
	while(!q.empty()) {
		int ja = q.top().se;
		q.pop();
		if(odw[ja]) continue;
		odw[ja] = 1;
		path[ja] = min(path[ja], dis[0][ja]);
		if(odl[ja] + dis[2][ja] == dis[2][t])
			ans = min(ans, dis[1][ja] + path[ja]);
		for(auto it : v[ja]) {
			ll nowa = odl[ja] + it.se;
			if(nowa < odl[it.fi]) {
				odl[it.fi] = nowa;
				path[it.fi] = path[ja];
				q.push(mp(-nowa, it.fi));
			}
			else if(nowa == odl[it.fi]) {
				path[it.fi] = min(path[it.fi], path[ja]);
			}
		}
	}
}
				
	
	

int main() {
	scanf("%d %d", &n, &m);
	scanf("%d %d", &s, &t);
	scanf("%d %d", &uu, &vv);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, c));
	}
	dij(uu, 0);
	dij(vv, 1);
	dij(s, 2);
	
	ans = min(ans, dis[0][vv]);
	algo();
	for(int i = 1; i <= n; ++i)
		swap(dis[0][i], dis[1][i]);
	algo();
	printf("%lld\n", ans);
	
	
	
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:85: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:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &s, &t);
  ~~~~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &uu, &vv);
  ~~~~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:89:8: 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