Submission #1050139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050139		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	167 ms	18472 KiB

commuter_pass

#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("03")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("03,fast-math")
#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end())
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int INF = 1e17;
int n, m, s, t, u1, v1;



void solve() {
    cin >> n >> m;
    cin >> s >> t;
    cin >> u1 >> v1;
    vector <vector<pair<int,int>>> g(n+1);
    for(int i=0; i<m; i++){
    	int from, to, cost;
    	cin>>from>>to>>cost;
    	g[from].pb({to, cost});
    	g[to].pb({from, cost});
    	
    }
    
    vector<int> d (n+1, INF);
    
    vector<pair<int,int>> p(n+1);
	d[s] = 0;
	set < pair<int,int> > q;
	q.insert (make_pair (d[s], s));
	while (!q.empty()) {
		int v = q.begin()->second;
		q.erase (q.begin());
 
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				q.erase (make_pair (d[to], to));
				d[to] = d[v] + len;
				p[to] = {v, len};
				q.insert (make_pair (d[to], to));
			}
		}
	}
	
	int tt = t;
	while(tt!=s){
		int f = p[tt].f, cost=p[tt].s;
		// cout<<f<<" ";
		for(int i=0; i<g[f].size(); i++){
			if(g[f][i].f==tt and g[f][i].s==cost){
				g[f][i].s=0;
				break;
			}
		}
		for(int i=0; i<g[tt].size(); i++){
			if(g[tt][i].f==f and g[tt][i].s==cost){
				g[tt][i].s=0;
				break;
			}
		}
		tt = f;
	}
	
	s = u1;
	d.clear();
	d.resize(n+1, INF);
	// vector<int> d (n+1, INF);
    p.clear();
    p.resize(n+1);
    // vector<pair<int,int>> p(n+1);
	d[s] = 0;
	// set < pair<int,int> > q;
	q.insert (make_pair (d[s], s));
	while (!q.empty()) {
		int v = q.begin()->second;
		q.erase (q.begin());
 
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				q.erase (make_pair (d[to], to));
				d[to] = d[v] + len;
				p[to] = {v, len};
				q.insert (make_pair (d[to], to));
			}
		}
	}
	cout<<d[v1];
}

signed main() {
    fast_io;
    int tc = 1;
    while (tc--)
        solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:66:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0; i<g[f].size(); i++){
      |                ~^~~~~~~~~~~~
commuter_pass.cpp:72:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0; i<g[tt].size(); i++){
      |                ~^~~~~~~~~~~~~

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