Submission #833266

#	Time	Username	Problem	Language	Result	Execution time	Memory
833266		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++98	15 / 100	363 ms	51412 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<ll,ll>

const ll N = 1e5+10;

ll n,m,u,v,s,t;
ll temp,a,b,c;
map<ll,bool> ada[N];
vector<pii> adj[N];
vector<ll> pass;
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool vis[N];
ll dist[N],pre[N];

void f(ll x) {
	if(pre[x] != 0) {
		f(pre[x]);
		pass.pb(x);
	}
}

int main() {
	cin >> n >> m;
	cin >> s >> t;
	cin >> u >> v;
	for(int i=1; i<=m; i++) {
		cin >> a >> b >> c;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	for(int i=1; i<=n; i++) dist[i] = 1e18;
	pq.push({0,s});
	dist[s] = 0;
	while(!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		for(auto i : adj[x.se]) {
			if(dist[i.fi] > dist[x.se] + i.se) {
				dist[i.fi] = dist[x.se] + i.se;
				pq.push({dist[i.fi],i.fi});
				pre[i.fi] = x.se;
			}
		}
	}
//	cout << "dist " << endl;
//	for(int i=1; i<=n; i++) {
//		cout << dist[i] << endl;
//	}
//	cout << "prev " << endl;
//	for(int i=1; i<=n; i++) {
//		cout << pre[i] << endl;
//	}
	pass.pb(s);
	f(t);
//	cout << "pass ";
//	for(auto i : pass) {
//		cout << i <<  " ";
//	}
//	cout << endl;
	for(int i=1; i<pass.size(); i++) {
		ada[pass[i-1]][pass[i]] = true;
		ada[pass[i]][pass[i-1]] = true;
	}
	for(int i=1; i<=n; i++) dist[i] = 1e18;
	pq.push({0,u});
	dist[u] = 0;
	while(!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		for(auto i : adj[x.se]) {
//			cout << "mat " << x.se << " " << i.fi << endl;
			if(ada[x.se][i.fi]) temp = 0;
			else temp = i.se;
//			cout << "temp " << temp << endl;
			if(dist[i.fi] > dist[x.se] + temp) {
				dist[i.fi] = dist[x.se] + temp;
				pq.push({dist[i.fi],i.fi});
			}
		}
	}
//	cout << "dist " << endl;
//	for(int i=1; i<=n; i++) {
//		cout << dist[i] << endl;
//	}
	cout << dist[v] << endl;
}

/*
3 3
1 2
2 3
1 2 1
1 3 1
2 3 3
*/

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=1; i<pass.size(); i++) {
      |               ~^~~~~~~~~~~~

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