oj.uz

Submission #158822

# Submission time Handle Problem Language Result Execution time Memory
158822 2019-10-18T22:27:30 Z GioChkhaidze Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 625 ms 25336 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N=2e5+5;

int n,m,S,T,U,V;
long long D[N][4],dp[N],fix[N];
vector < pair < long long  , int > > v[N];

void Dijkstra(int type) {
	multiset < pair < long long , int > > st;
	for (int i=1; i<=n; i++) 
		fix[i]=0,D[i][type]=1e17;
	
	if (!type) D[V][0]=0,st.insert({D[V][0],V});
		else 
	if (type==1) D[U][1]=0,st.insert({D[U][1],U});
		else
	if (type==2) D[S][2]=0,st.insert({D[S][3],S});
		else
	if (type==3) D[T][3]=0,st.insert({D[T][3],T});
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;
		for (int i=0; i<v[x].size(); i++){
			long long to=v[x][i].F,dist=v[x][i].S;
			if (!fix[to] && D[x][type]+dist<D[to][type]) {
				D[to][type]=D[x][type]+dist;
				st.insert({D[to][type],to});
			}
		}
	}
}

void FillDp(int type) {
	multiset < pair < long long , int > > st;
	long long d[N];

	for (int i=1; i<=n; i++) 
		fix[i]=0,d[i]=1e17,dp[i]=1e17;


	if (!type) {
		d[T]=0,dp[T]=D[T][0];
		st.insert({d[T],T});
	}
		else {
		d[S]=0,dp[S]=D[S][0];
		st.insert({d[S],S});	
	}
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;

		for (int i=0; i<v[x].size(); i++) {
			long long to=v[x][i].F,dist=v[x][i].S;
			if (!fix[to] && d[x]+dist<d[to] && D[to][2]+D[to][3]==D[S][3]) {
				dp[to]=min(dp[x],D[to][0]);
				d[to]=d[x]+dist;
				st.insert({d[to],to});
			}
		}
	}
}

main () {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	cin>>S>>T;
	cin>>U>>V;
	
	for (int i=1; i<=m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	
	Dijkstra(0);
	Dijkstra(1);
	Dijkstra(2);
	Dijkstra(3);
	FillDp(0);
	
	long long ANS=D[V][1];

	for (int x=1; x<=n; x++) 
		ANS=min(ANS,dp[x]+D[x][1]);

	FillDp(1);

	for (int x=1; x<=n; x++) 
		ANS=min(ANS,dp[x]+D[x][1]);
	
	cout<<ANS<<endl;
}

Compilation message

commuter_pass.cpp: In function 'void Dijkstra(int)':
commuter_pass.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++){
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void FillDp(int)':
commuter_pass.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<v[x].size(); i++) {
                 ~^~~~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:76:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 24936 KB Output is correct
2 Correct 510 ms 24312 KB Output is correct
3 Correct 578 ms 24948 KB Output is correct
4 Correct 575 ms 24944 KB Output is correct
5 Correct 513 ms 23840 KB Output is correct
6 Correct 572 ms 25336 KB Output is correct
7 Incorrect 499 ms 24312 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 24636 KB Output is correct
2 Correct 583 ms 24056 KB Output is correct
3 Correct 532 ms 24056 KB Output is correct
4 Correct 548 ms 24064 KB Output is correct
5 Correct 582 ms 24184 KB Output is correct
6 Correct 551 ms 24440 KB Output is correct
7 Correct 603 ms 24056 KB Output is correct
8 Correct 580 ms 24312 KB Output is correct
9 Correct 556 ms 24056 KB Output is correct
10 Correct 597 ms 24128 KB Output is correct
11 Correct 337 ms 15836 KB Output is correct
12 Correct 625 ms 24824 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 6392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 24936 KB Output is correct
2 Correct 510 ms 24312 KB Output is correct
3 Correct 578 ms 24948 KB Output is correct
4 Correct 575 ms 24944 KB Output is correct
5 Correct 513 ms 23840 KB Output is correct
6 Correct 572 ms 25336 KB Output is correct
7 Incorrect 499 ms 24312 KB Output isn't correct
8 Halted 0 ms 0 KB -