oj.uz

Submission #48434

# Submission time Handle Problem Language Result Execution time Memory
48434 2018-05-13T12:08:26 Z aleksami Commuter Pass (JOI18_commuter_pass) C++14
0 / 100
 487 ms 81376 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
#define INF 1000000000
typedef pair<int,int> pii;
vector <pii> g[MAXN];
bool gotov[MAXN];
priority_queue <pii> pq;
int n,m;

void dijkstra(int *d,int source)
{
	for(int i = 0; i < MAXN; i++)d[i]=INF,gotov[i]=false;
	d[source]=0;
	pq.push({-d[source],source});
	while(!pq.empty())
	{
		int v = pq.top().second;
		pq.pop();
		if(gotov[v])continue;
		gotov[v]=1;
		for(auto x:g[v])
		{
			int u = x.first;
			int c = x.second;
			if(d[u]>d[v]+c)d[u]=d[v]+c,pq.push({-d[u],u});
		}
	}
}
int ds[MAXN];
int dt[MAXN];
int du[MAXN];
int dv[MAXN];
int d1[MAXN];
int d2[MAXN];
int s,t;

void dijkstraa(int *d,int *dd)
{
	for(int i = 0; i < MAXN; i++)gotov[i]=false,dd[i]=d[i],pq.push({-dd[i],i});
	while(!pq.empty())
	{
		int v = pq.top().second;
		pq.pop();
		if(gotov[v])continue;
		gotov[v]=1;
		for(auto x:g[v])
		{
			int u = x.first;
			int c = x.second;
			if( ds[u]+c+dt[v]==ds[t] && dd[u]>dd[v])dd[u]=dd[v],pq.push({-dd[u],u});
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	int u,v;
	cin >> n >> m >> s >> t >> u >> v;
	for(int i = 0; i < m; i++)
	{
		int x,y,c;
		cin >> x >> y >> c;
		g[x].push_back({y,c});
		g[y].push_back({x,c});
	}
	dijkstra(ds,s);
	dijkstra(dt,t);
	dijkstra(du,u);
	dijkstra(dv,v);
	dijkstraa(dv,d1);
	dijkstraa(du,d2);
	int ans = INF;
	for(int i = 1; i <= n; i++)
	{
		ans=min(ans,du[i]+d1[i]);
		ans=min(ans,dv[i]+d2[i]);
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 16236 KB Output is correct
2 Correct 433 ms 19952 KB Output is correct
3 Correct 411 ms 23780 KB Output is correct
4 Correct 393 ms 27820 KB Output is correct
5 Correct 451 ms 31068 KB Output is correct
6 Correct 452 ms 35036 KB Output is correct
7 Correct 444 ms 38396 KB Output is correct
8 Correct 448 ms 41988 KB Output is correct
9 Incorrect 212 ms 46196 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 50056 KB Output is correct
2 Correct 487 ms 53540 KB Output is correct
3 Correct 472 ms 56932 KB Output is correct
4 Correct 472 ms 60320 KB Output is correct
5 Correct 479 ms 63856 KB Output is correct
6 Correct 456 ms 67496 KB Output is correct
7 Correct 486 ms 71152 KB Output is correct
8 Correct 482 ms 74548 KB Output is correct
9 Correct 465 ms 78120 KB Output is correct
10 Correct 475 ms 81376 KB Output is correct
11 Incorrect 116 ms 81376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 81376 KB Output is correct
2 Incorrect 32 ms 81376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 16236 KB Output is correct
2 Correct 433 ms 19952 KB Output is correct
3 Correct 411 ms 23780 KB Output is correct
4 Correct 393 ms 27820 KB Output is correct
5 Correct 451 ms 31068 KB Output is correct
6 Correct 452 ms 35036 KB Output is correct
7 Correct 444 ms 38396 KB Output is correct
8 Correct 448 ms 41988 KB Output is correct
9 Incorrect 212 ms 46196 KB Output isn't correct
10 Halted 0 ms 0 KB -