제출 #1223824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223824		Bui_Quoc_Cuong	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	264 ms	21600 KiB

commuter_pass

// #pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int MAXN = 3e5 + 5;
const long long INF = 1e18;

int n, m, ST, ED, U, V;
struct Edges{
	int u, v, w;
} E[MAXN];
long long dist1[MAXN], dist2[MAXN];
vector <pair <int, int>> g[MAXN];
long long dist[MAXN];

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    file("BUS");

    cin >> n >> m >> ST >> ED >> U >> V;
	FOR(i, 1, m){
		cin >> E[i].u >> E[i].v >> E[i].w;
		g[E[i].u].push_back(make_pair(E[i].v, E[i].w));
		g[E[i].v].push_back(make_pair(E[i].u, E[i].w));
	}    

	auto dijk = [&](int st, long long dist[]){
		FOR(i, 1, n) dist[i] = INF;
		#define pli pair <long long, int>
		priority_queue <pli, vector <pli>, greater <pli>> pq;
		pq.push({dist[st] = 0, st});
		while(!pq.empty()){
			int u = pq.top().second;
			long long cost = pq.top().first;
			pq.pop();
			if(cost > dist[u]) continue;
			for(const pair <int, int> &x : g[u]){
				int v = x.first, w = x.second;
				if(dist[v] > cost + w){
					dist[v] = cost + w;
					pq.push({dist[v], v});
				}
			}
		}
	};

	dijk(ST, dist1);
	dijk(ED, dist2);	

	auto dijkdag = [&](int st, int ed){
		priority_queue <pli, vector <pli>, greater <pli>> pq;
		vector <long long> dist(n + 2);
		FOR(i, 1, n) dist[i] = INF;		

		pq.push({dist[st] = 0, st});
		while(!pq.empty()){
			int u = pq.top().second;
			long long cost = pq.top().first;
			pq.pop();
			if(cost > dist[u]) continue;
			for(auto x : g[u]){
				int v = x.first, w = x.second;
				w = (dist1[u] + w + dist2[v] == dist1[ED] ? 0 : w);
				if(dist[v] > cost + w){
					dist[v] = cost + w;
					pq.push({dist[v], v});
				} 
			}
		}

		return dist[ed];
	};	
	cout << min(dijkdag(U, V), dijkdag(V, U));

    return void(cerr << "\nKO: " << 0.001 * clock() << "s "), 0;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:23:5: note: in expansion of macro 'file'
   23 |     file("BUS");
      |     ^~~~
commuter_pass.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:23:5: note: in expansion of macro 'file'
   23 |     file("BUS");
      |     ^~~~

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