Submission #526865

#	Time	Username	Problem	Language	Result	Execution time	Memory
526865		zhangjishen	Commuter Pass (JOI18_commuter_pass)	C++98	100 / 100	349 ms	22524 KiB

commuter_pass

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

#define mp make_pair
#define pb push_back
#define fi first 
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
const ll inf = 1e18;

int n, m, S, T, U, V;
vector<pii> adj[MAXN];
ll ds[MAXN], dt[MAXN], du[MAXN], dv[MAXN], fs[MAXN], ft[MAXN];

// SP with source s store to f
priority_queue<pli, vector<pli>, greater<pli> > q;
void SP(int s, ll f[]){
	for(int i = 1; i <= n; i++)
		f[i] = inf;
	f[s] = 0; q.push(mp(0, s));
	while(!q.empty()){
		pli p = q.top(); q.pop();
		int u = p.se;
		if(p.fi != f[u]) continue;
		for(int i = 0; i < (int)adj[u].size(); i++){
			int v = adj[u][i].fi, w = adj[u][i].se;
			if(chkmin(f[v], f[u] + w))
				q.push(mp(f[v], v));
		}
	}
}

// f[u]: SP s -> u with min dis to U
void DP(ll d[], ll f[]){
	vector<pli> topo;
	for(int i = 1; i <= n; i++)
		topo.pb(mp(d[i], i));
	sort(topo.begin(), topo.end());
	for(int i = 0; i < n; i++){
		int u = topo[i].se;
		f[u] = du[u];
		for(int j = 0; j < (int)adj[u].size(); j++){
			int v = adj[u][j].fi, w = adj[u][j].se;
			if(d[v] + w == d[u])
				chkmin(f[u], f[v]);
		}
	}
}

int main(){
	// input
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &S, &T, &U, &V);
	int a, b, c;
	for(int i = 1; i <= m; i++){
		scanf("%d %d %d", &a, &b, &c);
		adj[a].pb(mp(b, c));
		adj[b].pb(mp(a, c));
	}
	// dijkstra
	SP(S, ds); SP(T, dt);
	SP(U, du); SP(V, dv);
	// DP
	DP(ds, fs); DP(dt, ft);
	// find ans
	ll ans = du[V];
	for(int i = 1; i <= n; i++)	// i on SP s -> t
		if(ds[i] + dt[i] == ds[T])
			chkmin(ans, dv[i] + min(fs[i], ft[i]));
	printf("%lld\n", ans);
}

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]
   57 |  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]
   58 |  scanf("%d%d%d%d", &S, &T, &U, &V);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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