oj.uz

Submission #786922

# Submission time Handle Problem Language Result Execution time Memory
786922 2023-07-18T14:47:15 Z Acanikolic Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 420 ms 42416 KB 
#include <bits/stdc++.h>
 
#define ll long long 

#define int long long 
 
#define pb push_back 

#define F first
 
#define S second
 
using namespace std;
 
const long long N = 1e5+10;
 
const long long mod = 1e9+7;
 
const long long inf = 1e18;

vector<pair<int,int>>g[N];

map<pair<int,int>,bool>mark;

void dijkstra(int node,int end) {
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,node});
	vector<int>dist(N,inf),vis(N,0),par(N,-1);
	dist[node] = 0;
	while(pq.size()) {
		int cost,u;
		u = pq.top().S;
		cost = pq.top().F;
		pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto X:g[u]) {
			if(cost+X.S < dist[X.F]) {
				par[X.F] = u;
				dist[X.F] = cost+X.S;
				pq.push({dist[X.F],X.F});
			}
		}
	}
	int cvor = end;
	while(cvor != -1) {
		mark[{cvor,par[cvor]}] = 1;
		mark[{par[cvor],cvor}] = 1;
		cvor = par[cvor];
	}
}

int Dij(int start,int end) {
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,start});
	vector<int>dist(N,inf),vis(N,0),par(N,-1);
	dist[start] = 0;
	while(pq.size()) {
		int cost,u;
		u = pq.top().S;
		cost = pq.top().F;
		pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto X:g[u]) {
			if(mark[{u,X.F}]) {
				if(dist[X.F] > dist[u]) {
					dist[X.F] = dist[u];
					pq.push({dist[X.F],X.F});
				}
			}
			else {
				if(dist[X.F] > dist[u]+X.S) {
					dist[X.F] = dist[u]+X.S;
					pq.push({dist[X.F],X.F});
				}
			}
		}
	}
	/*for(int i=1;i<=end;i++) cout << dist[i] << ' ';
	cout << endl;*/	
	return dist[end];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
   	int n,m,s,t,u,v;
   	cin >> n >> m >> s >> t >> u >> v;
   	for(int i=1;i<=m;i++) {
   		int u,v,w;
   		cin >> u >> v >> w;
   		g[u].pb({v,w});
   		g[v].pb({u,w});
   	}
   	dijkstra(s,t);
   	cout << Dij(u,v);
   	//for(auto X:mark) cout << X.F.F << ' ' << X.F.S << endl;
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'long long int Dij(long long int, long long int)':
commuter_pass.cpp:59:7: warning: variable 'cost' set but not used [-Wunused-but-set-variable]
   59 |   int cost,u;
      |       ^~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 42128 KB Output is correct
2 Correct 343 ms 42096 KB Output is correct
3 Correct 333 ms 42108 KB Output is correct
4 Incorrect 358 ms 42076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 42084 KB Output is correct
2 Correct 324 ms 42028 KB Output is correct
3 Correct 318 ms 42308 KB Output is correct
4 Correct 386 ms 42076 KB Output is correct
5 Correct 353 ms 42056 KB Output is correct
6 Correct 419 ms 41996 KB Output is correct
7 Correct 411 ms 42416 KB Output is correct
8 Correct 420 ms 42028 KB Output is correct
9 Correct 395 ms 42068 KB Output is correct
10 Correct 382 ms 42076 KB Output is correct
11 Correct 179 ms 23740 KB Output is correct
12 Correct 401 ms 42036 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 42128 KB Output is correct
2 Correct 343 ms 42096 KB Output is correct
3 Correct 333 ms 42108 KB Output is correct
4 Incorrect 358 ms 42076 KB Output isn't correct
5 Halted 0 ms 0 KB -