Submission #444017

#	Time	Username	Problem	Language	Result	Execution time	Memory
444017		test_account123	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	422 ms	30908 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e17;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>
#define PQ priority_queue<int>

void setIO(string d_name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(d_name)){
		freopen((d_name+".in").c_str(), "r", stdin);
		freopen((d_name+".out").c_str(), "w", stdout);
	}
}

Vpii adj[100001];

void dijkstra1(int start, Vi& dist)
{
	dist[start]= 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push(mp(0, start));
	while(!pq.empty())
	{
		int d, x;
		tie(d, x)= pq.top();
		pq.pop();
		if(dist[x] != d)
		{
			continue;
		}
		for(auto e: adj[x])
		{
			if(dist[e.fi] > dist[x] + e.se)
			{
				dist[e.fi]= dist[x]+e.se;
				pq.push(mp(dist[e.fi], e.fi));
			}
		}
	}
}

int dijkstra2(int start, int end, Vi& dist1, Vi& dist2)
{
	Vi dist(100001);
	Vi visited(100001);
	Vi mi1(100001, INF);
    Vi mi2(100001, INF);
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push(mp(0, mp(start, 0)));
	while(!pq.empty())
	{
		int d, x, p;
		pair<int, pair<int, int>> t= pq.top();
		pq.pop();
		d= t.fi;
		x= t.se.fi;
		p= t.se.se;
		if(!visited[x])
		{
			visited[x]= 1;
			dist[x]= d;
			mi1[x]= min(dist1[x], mi1[p]);
			mi2[x]= min(dist2[x], mi2[p]);
			for(auto e: adj[x])
			{
				pq.push(mp(dist[x]+e.se, mp(e.fi, x)));
			}
		}
		else if(dist[x] == d)
		{
			if((min(mi1[p], dist1[x]) + min(mi2[p], dist2[x])) < (mi1[x] + mi2[x]))
			{
				mi1[x]= min(mi1[p], dist1[x]);
				mi2[x]= min(mi2[p], dist2[x]);
			}
		}
	}
	return (mi1[end] + mi2[end]);
}

int32_t main()
{
    setIO();
    int n, m;
    cin>>n>>m;
    int s, t;
    cin>>s>>t;
    int u, v;
    cin>>u>>v;
    rep(_,0,m)
    {
    	int a, b, c;
    	cin>>a>>b>>c;
    	adj[a].pb(mp(b, c));
    	adj[b].pb(mp(a, c));
    }
    Vi dist1(n+1, INF);
    Vi dist2(n+1, INF);
    dijkstra1(u, dist1);
    dijkstra1(v, dist2);
    int ans= dist1[v];
    ans= min(ans, dijkstra2(s, t, dist1, dist2));
    cout<<ans;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   freopen((d_name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen((d_name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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