Submission #1062006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062006		_rain_	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	442 ms	31104 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false
 
void SETIO(string name)
{
	if (name=="") return;
	freopen((name + ".inp").c_str(),"r",stdin);
	freopen((name + ".out").c_str(),"w",stdout);
	return;
}
 
const int maxn = 2e5;
const i64 INF = 1e18;
vector<pair<int,int>> g[maxn+2];
int u[maxn+2],v[maxn+2],c[maxn+2];
#define fi first
#define se second
int n , m , source , sink , nsource , nsink;
 
struct _D
{
	i64 val;
	i64 rem;
	int u;
	int t;
	bool operator <(const _D & other) const {
		if (other.val != val) return other.val < val;
		if (other.rem != rem) return other.rem < rem;
	}
} ;
bool vis[maxn+2][2];
vector<i64> dist[2];
i64 dp[maxn+2][2];
i64 mn ;
 
vector<i64> djisktra(int source)
{
	vector<i64> d; d.assign(n+2,INF);
	d[source] = 0;
	priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> q;
	q.push({d[source] , source});
	while (q.size())
	{
		int u = q.top().se;
		i64 val = q.top().fi;
		q.pop();
		if (d[u] != val) continue;
		for (auto& v : g[u])
		{
			if (d[v.first] > d[u] + v.second)
			{
				d[v.first] = d[u] + v.second;
				q.push({d[v.first] , v.first});
			}
		}
	}
	return d;
}
 
int trans(int v , int t , int t1 , int t2){
	if (t==1) return t;
	if (t==0){
		if (dist[t1][v] + dist[t2][v] == mn) return 1;
	}
	return 0;
}
i64 cost(int v , int w , i64 rem , int t , int t1 , int t2){
	if (t==0){
		if (dist[t1][v] + dist[t2][v] == mn) return 0;
		return w;
	}
	if (t==1){
		if (rem==INF) return w;
		if (dist[t1][v] + dist[t2][v] == mn && rem + w == dist[t1][v]) return 0;
		return w;
	}
	return INF;
}
 
i64 calc(int s , int snk , int t1 , int t2)
{
	memset(vis,0,sizeof vis);
	memset(dp,0x3f,sizeof dp);
	priority_queue<_D> q; int zz = trans(s,0,t1,t2);
	dp[s][zz] = 0;
	if (zz==1) q.push({dp[s][zz] , dist[t1][s] , s , 1});
		else q.push({dp[s][zz] , INF , s , 0});
	if (debug){
		cout << "START THE SEASON\n";
		cout << t1 << ' ' << t2 << '\n';
	}
	while (q.size()){
		int u = q.top().u , t = q.top().t;
		i64 val = q.top().val , rem = q.top().rem;
		q.pop();
		
		if (vis[u][t]) continue;
		vis[u][t]=true;
		dp[u][t]=val;
		
		if (debug){
			cout << "DEBUG\n";
			cout << dp[u][t] << ' ' << u << ' ' << t << '\n';	
		}
		for (auto& v : g[u]){
			int to = v.first , w = v.second;
			int nxt = trans(to , t , t1 , t2);
			if (vis[to][nxt]) continue;
			i64 c = cost(to , w , rem , t , t1 , t2);
			if (debug){
				cout << "( SHOW OUT FOR THE CASE : " << u << ')' << '\n';
				cout << u << " -> " << to << ' ' << w << ' ' << nxt << ' ' << c << '\n';
				cout << dist[t1][to] << ' ' << dist[t2][to] << ' ' << mn << '\n';
				cout << '\n';
			}
			if (t == 0){
				if (nxt==0) q.push({val + w , INF , to , 0});
					else q.push({val + w , dist[t1][to] , to , 1});
			}
			if (t == 1){
				if (c > 0) q.push({val + w , INF , to , 1});
					else q.push({val , dist[t1][to] , to , 1});
			}
		}
	}
	return min(dp[snk][0],dp[snk][1]);
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	SETIO("");
	
	cin >> n >> m;
	cin >> source >> sink;
	cin >> nsource >> nsink;
	for (int i = 1; i <= m; ++i){
		cin >> u[i] >> v[i] >> c[i];
		g[u[i]].push_back({v[i],c[i]});
		g[v[i]].push_back({u[i],c[i]});
	}	
	dist[0] = djisktra(source); 
	dist[1] = djisktra(sink);
	mn = dist[0][sink];
	if (debug){
		cout << "MINIMUM DIST : " << mn << '\n';
	}
	cout << min({calc(nsource,nsink,0,1),calc(nsource , nsink,1,0),calc(nsink,nsource,0,1),calc(nsink,nsource,1,0)});
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void SETIO(std::string)':
commuter_pass.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen((name + ".inp").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((name + ".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In member function 'bool _D::operator<(const _D&) const':
commuter_pass.cpp:31:2: warning: control reaches end of non-void function [-Wreturn-type]
   31 |  }
      |  ^

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