제출 #930330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930330		lovrot	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	421 ms	19036 KiB

commuter_pass

#include <algorithm> 
#include <set> 
#include <vector> 
#include <cstdio> 

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10; 
const ll OO = 1e18;

int n, m, s, t, p, k;
vector<pii> G[N];

ll DP[N];
vector<int> DAG[N];

ll D[N];

auto comp = [](int a, int b) { return D[a] < D[b] || (D[a] == D[b] && a < b); };
set<int, decltype(comp)> S(comp); 

void dijkstra(int s, vector<ll> &V) {
	for(int i = 1; i <= n; ++i) D[i] = OO;
	D[s] = 0;
	S.insert(s);

	for(; !S.empty(); ) {
		int u = *S.begin();
		S.erase(S.begin()); 

		for(pii e : G[u]) 
			if(D[e.X] > D[u] + e.Y) {
				S.erase(e.X);
				D[e.X] = D[u] + e.Y;
				S.insert(e.X);
			}
	}
	
	V.resize(N);
	for(int i = 1; i <= n; ++i) V[i] = D[i];
}

vector<int> V;
vector<ll> DS, DT, DK, DST;

int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &p, &k);
	for(int i = 0; i < m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w); 
		G[u].PB({v, w});
		G[v].PB({u, w});
	}

	dijkstra(s, DS); 
	dijkstra(t, DT);
	dijkstra(k, DK);

	for(int i = 1; i <= n; ++i) {
		V.PB(i); 
		DP[i] = OO;
	}

	sort(V.begin(), V.end(), [](int a, int b) { return DS[a] > DS[b]; });
	for(int u : V) {
		DP[u] = min(DP[u], DK[u]);
		for(pii e : G[u]) 
			if(DS[u] + e.Y + DT[e.X] == DS[t]) {
				DP[u] = min(DP[u], DP[e.X]);
//				printf("%d -> %d\n", u, e.X);
			}
	}

	sort(V.begin(), V.end(), [](int a, int b) { return DT[a] > DT[b]; });
	for(int u : V) {
		DP[u] = min(DP[u], DK[u]);
		for(pii e : G[u]) 
			if(DT[u] + e.Y + DS[e.X] == DT[s]) {
				DP[u] = min(DP[u], DP[e.X]);
//				printf("%d -> %d\n", u, e.X);
			}
	}

	ll ans = OO;
	dijkstra(p, DST);
	
//	for(int u = 1; u <= n; ++u) printf("%d: s %lld t %lld u %lld v %lld dp %lld\n", u, DS[u], DT[u], DST[u], DK[u], DP[u]);
	for(int u = 1; u <= n; ++u) ans = min(ans, DST[u] + DP[u]);

	printf("%lld\n", ans);
	return 0;
}

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &p, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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