Submission #1287156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287156		herominhsteve	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	245 ms	28372 KiB

commuter_pass

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "JOI18_commuter_pass"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1e5 + 5;
const long long INF = (long long) 1e16 + 15092007;

struct Edges{
	int v;
	long long w;
	Edges(): v(0),w(0) {}
	Edges(int V,long long W):v(V),w(W) {}
	bool operator < (const Edges &other) const{
		return w>other.w;
	}
};

int n,m;
int S,T,U,V;
vector<Edges> graph[MAXN];

void init(){
	cin>>n>>m;
	cin>>S>>T>>U>>V;
	for (int i=0;i<m;i++){
		int u,v;
		long long w;
		cin>>u>>v>>w;
		graph[u].emplace_back(v,w);
		graph[v].emplace_back(u,w);
	}
}

vector<long long> disS,disT,disU,disV;

void Dijkstra(int s,vector<long long> &distancia){
	distancia.assign(n+1,INF);
	distancia[s] = 0;
	priority_queue<Edges> pq;
	pq.emplace(s,0);

	while (!pq.empty()){
		int u = pq.top().v;
		long long dis = pq.top().w;
		pq.pop();
		if (dis > distancia[u]) continue;
		for (const Edges &x : graph[u]){
			int v = x.v;
			long long newdis = x.w;
			if (minimize(distancia[v],dis + newdis)){
				pq.emplace(v,distancia[v]);
			}
		}
	}
}

long long disST;
vector<bool> visited;

/*
 * dp[x][0/1]:
 * 0: min(dist(U,x)) (x is reached after U)
 * 1: min(dist(V,x)) (x is reached after V)
*/
vector<vector<long long>> dp;

long long res;

void dfs(int u){
	visited[u] = 1;
	dp[u][0] = disU[u];
	dp[u][1] = disV[u];

	for (const Edges &x : graph[u]){
		int v = x.v;
		long long w = x.w;
		if (disS[v] + disT[v]==disST and disS[v] == disS[u] + w){
			if (!visited[v]) dfs(v);
			minimize(dp[u][0],dp[v][0]);
			minimize(dp[u][1],dp[v][1]);
		}
	}

	minimize(res,dp[u][0] + disV[u]);
	minimize(res,dp[u][1] + disU[u]);
	
}

void sol(){
	Dijkstra(S,disS);
	Dijkstra(T,disT);
	Dijkstra(U,disU);
	Dijkstra(V,disV);

	disST = disS[T];
	visited.assign(n+1,0);

	res = disU[V];
	dp.assign(n+1,vector<long long>(2,INF));
	dfs(S);
	cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setup()':
commuter_pass.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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