Submission #1014098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014098		pacman	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	348 ms	24404 KiB

commuter_pass

/******************************************************
| '_ \ / _` |/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | (__| | | | | | (_| | | | |
| .__/ \__,_|\___|_| |_| |_|\__,_|_| |_|
|_|

__|      |____________________________________________
     ,--.    ,--.          ,--.   ,--.
    |oo  | _  \  `.       | oo | |  oo|
o  o|~~  |(_) /   ;       | ~~ | |  ~~|o  o  o  o  o
    |/\/\|   '._,'        |/\/\| |/\/\|
__________________        ____________________________
******************************************************/

#include <bits/stdc++.h>
//#include "bigint.h"
#define db(x) cerr << #x << ": " << x << endl
#define print cerr << "Ah shit, here we go agian" << endl
#define int long long int
#define vii vector<int>
#define pii pair<int ,int>
#define vpi vector< pii >
#define ff first
#define ss second
#define mp make_pair
#define mod 1000000007

using namespace std;

const int maxn = 1e5 + 10 ,inf = 1e15;

int n ,m ,s ,t, st, ed;

set<pii> seti;
vpi adj[maxn];
int h[maxn] ,par[maxn];


inline void djkasra(){
	for(int i = 1 ; i <= n; i++){
		int v = (*seti.begin()).ss;
		seti.erase(seti.begin());
		for(auto [u ,w] : adj[v]){
			if(h[u] > (h[v] + w)){
				seti.erase(make_pair(h[u] ,u));
				h[u] = h[v] + w;
				par[u] = v;
				seti.insert(make_pair(h[u] ,u));
			}
		}
		if(seti.size() == 0) break;
	}
}


inline void f(int v){
	if(v == s){
		return;
	}
	
	int cnt = 0;
	for(auto i : adj[v]){
		if(i.ff == par[v]){
			adj[v][cnt].ss = 0;
		}
		cnt++;
	}
	cnt = 0;
	for(auto i : adj[par[v]]){
		if(i.ff == v){
			adj[par[v]][cnt].ss = 0;
		}
		cnt++;
	}
	f(par[v]);
}


signed main(){

	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);

	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	cin >> n >> m;
	cin >> s >> t;
	cin >> st >> ed;
	
	for(int i = 0 ; i < m; i++){
		int x, y ,z;
		cin >> x >> y >> z;
		
		adj[x].push_back({y ,z});
		adj[y].push_back({x ,z});
	}
	
	for(int i = 1 ; i <= n; i++){
		h[i] = inf;
	}
	
	h[s] = 0;
	
	for(int i = 1; i <= n; i++){
		seti.insert(make_pair(h[i] ,i));
	}

	djkasra();
	
	f(t);
	
	for(int i = 0 ;i <= n; i++){
		h[i] = 0;
		par[i]= 0;
	}
	seti.clear();
	
	for(int i = 1 ; i <= n; i++){
		h[i] = inf;
	}
	
	h[st] = 0;
	
	for(int i = 1; i <= n; i++){
		seti.insert(make_pair(h[i] ,i));
	}
	
	djkasra();
	
	cout << h[ed] << endl;
	
	cout << endl;
	
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void djkasra()':
commuter_pass.cpp:43:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   for(auto [u ,w] : adj[v]){
      |            ^

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