Submission #833449

#	Time	Username	Problem	Language	Result	Execution time	Memory
833449		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	310 ms	32412 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define tll tuple<ll, ll, ll>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
using namespace std;
const ll INF=1e15;
const ll MX=200010;
//C
ll n, m, s, t, u, v, a[MX], b[MX], c[MX], dist[MX], pred[MX], ans;
vector<tll> adj[MX];
vector<ll> gbs[100002];
bool vis[MX];

void dijkstra1(){
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for(ll i=1; i<=n; i++){
		if(i==s) dist[i]=0;
		else dist[i]=INF;
		vis[i]=0;
	}
	pq.push({0, s});
	while(!pq.empty()){
		ll cn=g1(pq.top());
		ll cd=g0(pq.top()); 
//		vis[cn]=1;
		pq.pop();

		for(auto i : adj[cn]){
			ll w=g0(i), nxt=g1(i), idx=g2(i);
//			if(vis[nxt]) continue;
			if(cd+w>=dist[nxt]) continue;
			dist[nxt]=cd+w;
			pred[nxt]=cn;
//			vis[nxt]=1;
			pq.push({dist[nxt], nxt});
		}
	}
}

void dijkstra2(){
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for(ll i=1; i<=n; i++){
		if(i==u) dist[i]=0;
		else dist[i]=INF;
		vis[i]=0;
	}
	pq.push({0, u});
	while(!pq.empty()){
		ll cn=g1(pq.top());
		ll cd=g0(pq.top());         
		pq.pop();

//		cout << "adj " << cn << endl;
		for(auto i : adj[cn]){
			ll w=0, nxt=g1(i), idx=g2(i);
			if(find(gbs[cn].begin(), gbs[cn].end(), nxt)!=gbs[cn].end()){
				w=0;
			} 
			else w=c[idx];
//			cout << cn << " " << nxt << " " << w << endl;
			if(cd+w>=dist[nxt]) continue;
			dist[nxt]=cd+w;
			pq.push({dist[nxt], nxt});
		}
	}
}

int main(){
	cin >> n >> m >> s >> t >> u >> v;
	for(ll i=1; i<=m; i++){
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].pb({c[i], b[i], i});
		adj[b[i]].pb({c[i], a[i], i});
	}
	
	//shortest path 1 -> dari s ke t
	dijkstra1();
	
	ll cur=t, prev;
	while(cur!=s){
//		cout << cur << endl;
		prev=pred[cur];
		gbs[prev].pb(cur);
		gbs[cur].pb(prev);
		cur=prev;
	}

	//shortest path 2 -> dari u ke v
	dijkstra2();
	
	cout << dist[v] << endl;
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra1()':
commuter_pass.cpp:35:27: warning: unused variable 'idx' [-Wunused-variable]
   35 |    ll w=g0(i), nxt=g1(i), idx=g2(i);
      |                           ^~~

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