Submission #786922

#	Time	Username	Problem	Language	Result	Execution time	Memory
786922		Acanikolic	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	420 ms	42416 KiB

commuter_pass

#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 (stderr)

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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45