oj.uz

답안 #444017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444017 2021-07-13T01:55:47 Z test_account123 Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 422 ms 30908 KB 
#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

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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 30908 KB Output is correct
2 Correct 351 ms 29156 KB Output is correct
3 Correct 343 ms 25972 KB Output is correct
4 Correct 368 ms 30748 KB Output is correct
5 Correct 327 ms 25652 KB Output is correct
6 Correct 370 ms 30680 KB Output is correct
7 Correct 341 ms 28772 KB Output is correct
8 Correct 328 ms 28848 KB Output is correct
9 Correct 415 ms 29716 KB Output is correct
10 Correct 318 ms 29764 KB Output is correct
11 Correct 117 ms 14644 KB Output is correct
12 Correct 405 ms 29640 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 348 ms 29048 KB Output is correct
2 Correct 341 ms 25892 KB Output is correct
3 Correct 341 ms 25856 KB Output is correct
4 Correct 346 ms 25832 KB Output is correct
5 Correct 340 ms 25892 KB Output is correct
6 Correct 366 ms 25988 KB Output is correct
7 Correct 366 ms 25720 KB Output is correct
8 Correct 375 ms 25912 KB Output is correct
9 Correct 335 ms 25804 KB Output is correct
10 Correct 353 ms 25816 KB Output is correct
11 Correct 116 ms 14720 KB Output is correct
12 Correct 341 ms 26080 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8396 KB Output is correct
2 Correct 4 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 40 ms 10944 KB Output is correct
5 Correct 21 ms 9184 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct
8 Correct 6 ms 6220 KB Output is correct
9 Correct 5 ms 5964 KB Output is correct
10 Correct 20 ms 8400 KB Output is correct
11 Correct 4 ms 5836 KB Output is correct
12 Correct 4 ms 5836 KB Output is correct
13 Correct 4 ms 5836 KB Output is correct
14 Correct 4 ms 5836 KB Output is correct
15 Correct 5 ms 5836 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 30908 KB Output is correct
2 Correct 351 ms 29156 KB Output is correct
3 Correct 343 ms 25972 KB Output is correct
4 Correct 368 ms 30748 KB Output is correct
5 Correct 327 ms 25652 KB Output is correct
6 Correct 370 ms 30680 KB Output is correct
7 Correct 341 ms 28772 KB Output is correct
8 Correct 328 ms 28848 KB Output is correct
9 Correct 415 ms 29716 KB Output is correct
10 Correct 318 ms 29764 KB Output is correct
11 Correct 117 ms 14644 KB Output is correct
12 Correct 405 ms 29640 KB Output is correct
13 Correct 348 ms 29048 KB Output is correct
14 Correct 341 ms 25892 KB Output is correct
15 Correct 341 ms 25856 KB Output is correct
16 Correct 346 ms 25832 KB Output is correct
17 Correct 340 ms 25892 KB Output is correct
18 Correct 366 ms 25988 KB Output is correct
19 Correct 366 ms 25720 KB Output is correct
20 Correct 375 ms 25912 KB Output is correct
21 Correct 335 ms 25804 KB Output is correct
22 Correct 353 ms 25816 KB Output is correct
23 Correct 116 ms 14720 KB Output is correct
24 Correct 341 ms 26080 KB Output is correct
25 Correct 25 ms 8396 KB Output is correct
26 Correct 4 ms 5836 KB Output is correct
27 Correct 4 ms 5836 KB Output is correct
28 Correct 40 ms 10944 KB Output is correct
29 Correct 21 ms 9184 KB Output is correct
30 Correct 5 ms 5964 KB Output is correct
31 Correct 5 ms 6092 KB Output is correct
32 Correct 6 ms 6220 KB Output is correct
33 Correct 5 ms 5964 KB Output is correct
34 Correct 20 ms 8400 KB Output is correct
35 Correct 4 ms 5836 KB Output is correct
36 Correct 4 ms 5836 KB Output is correct
37 Correct 4 ms 5836 KB Output is correct
38 Correct 4 ms 5836 KB Output is correct
39 Correct 5 ms 5836 KB Output is correct
40 Correct 365 ms 30188 KB Output is correct
41 Correct 422 ms 29524 KB Output is correct
42 Correct 369 ms 29712 KB Output is correct
43 Correct 159 ms 14688 KB Output is correct
44 Correct 130 ms 14636 KB Output is correct
45 Correct 333 ms 25712 KB Output is correct
46 Correct 361 ms 25440 KB Output is correct
47 Correct 368 ms 27252 KB Output is correct
48 Correct 150 ms 14108 KB Output is correct
49 Correct 348 ms 29808 KB Output is correct
50 Correct 328 ms 25884 KB Output is correct
51 Correct 335 ms 25784 KB Output is correct