Submission #1050072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050072		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	242 ms	35248 KiB

commuter_pass

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <time.h>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <bits/stdc++.h>

#define speed ios_base::sync_with_stdio(0), cin.tie(0)
#define TxtIO freopen("points.in","r",stdin); freopen("points.out","w",stdout);
using namespace std;
const int mod = 1e9+7;
#define ll long long
const int N=2e5+5;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow (ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1)
			res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll fct[103];

ll cnk(ll n,ll k){
	return fct[n]*binpow(fct[k]*fct[n-k]%mod,mod-2)%mod;
}


void fcn(){
	ll n,m,s,t,st,en;
	cin>>n>>m>>s>>t>>st>>en;
	vector <vector <pair <ll,ll> > > g(n+3);
	
	for (int i=0; i<m; i++){
		ll x,y,c;
		cin>>x>>y>>c;
		g[x].push_back(make_pair(y,c));
		g[y].push_back(make_pair(x,c));
	}
	
	set <pair <ll,ll> > q;
	q.insert(make_pair(0,s));
	
	
	vector <ll> var(n+3,1e18),d(n+3,1e18),p(n+3);
	
	
	var[s]=1;
	d[s]=0;
	
	while (!q.empty()){
		ll v= (*q.begin()).second;
		q.erase(q.begin());
		for (int i=0; i<g[v].size(); i++){
			ll to=g[v][i].first,w=g[v][i].second;
			
			if (d[to]>d[v]+w){
				var[to]=var[v];
				p[to]=v;
				q.erase(make_pair(d[to],to));
				d[to]=d[v]+w;
				q.insert(make_pair(d[to],to));
			}else if(d[to]==d[v]+w){
				var[to]++;
			}
		}
		
	}
	
	
	
	
	if (var[t]==1){
		
		ll x=t;
		vector <vector <pair<ll,ll> > > g2 = g;
		while (x!=s){
			g2[p[x]].push_back(make_pair(x,0));
			g2[x].push_back(make_pair(p[x],0));
			x=p[x];
		}
		
		
		
		
		for (int i=0; i<=n; i++){
			d[i]=1e18;
		}
		
		d[st]=0;
		q.clear();
		q.insert(make_pair(0,st));
		while (!q.empty()){
			ll v=(*q.begin()).second;
			q.erase(q.begin());
			for (int i=0; i<g2[v].size(); i++){
				ll to=g2[v][i].first,w=g2[v][i].second;
//				cout<<v<<" "<<to<<" = "<<d[v]+w<<"\n";
				if (d[to]>d[v]+w){
					q.erase(make_pair(d[to],to));
					d[to]=d[v]+w;
					q.insert(make_pair(d[to],to));
				}
			}
			
		}
		cout<<d[en]<<"\n";
	}
	
	
	
	
	
	
	
	
}                        

int main(){
	//srand(time(0));
	//fflush(stdout);
//	freopen("bridges.in","r",stdin); freopen("bridges.out","w",stdout);

//	speed;
	ll T=1;
//	cin>>T;
	for (int i=1; i<=T; i++){
		fcn();	
	}
}




 

/*

1
2 3
4 5
6 7


*/

Compilation message (stderr)

commuter_pass.cpp: In function 'void fcn()':
commuter_pass.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int i=0; i<g[v].size(); i++){
      |                 ~^~~~~~~~~~~~
commuter_pass.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for (int i=0; i<g2[v].size(); i++){
      |                  ~^~~~~~~~~~~~~

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