Submission #93922

#	Time	Username	Problem	Language	Result	Execution time	Memory
93922		combi2k2	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	473 ms	24784 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pb  push_back
#define X   first
#define Y   second

const int   N   = 1e5 + 1;
const int   inf = 1e18;

typedef pair<int,int>   ii;

vector<ii>  g[N];

int n, m, k;
int d[20][N];

void INI(int s,int *dis)    {
	fill(dis + 1,dis + 1 + n,inf);
	dis[s] = 0;
	priority_queue<ii,vector<ii>,greater<ii> >  q;
	q.push({0,s});
	while(q.size())	{
		int u  = q.top().Y;
		int du = q.top().X;
		q.pop();
		if (du != dis[u])   continue;
		for(ii  e : g[u])   {
			int v = e.X;
			int C = e.Y;
			if (dis[v] > du + C)    {
				dis[v] = du + C;
				q.push({dis[v],v});
			}
		}
	}
}

int a[10], b[10];
int mask = 0;

int num[N];
int f[N];

signed main()   {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;  k = 2;
	
	for(int i = k - 1 ; i >= 0 ; --i)   {
		cin >> a[i] >> b[i];
		mask |= (1 << i);
	}
	
	while (m--) {
		int x, y, w;
		cin >> x >> y >> w;
		g[x].pb({y,w});
		g[y].pb({x,w});
	}
	
	//cin >> a[0] >> b[0];
	
	//for(int i = 1 ; i < k ; ++i)    {
	//	int x;  cin >> x;
	//	mask |= (x << i);
	//	cin >> a[i] >> b[i];
	//}
	
	for(int i = 0 ; i < k ; ++i)
		INI(a[i],d[i << 1]),
		INI(b[i],d[i << 1 | 1]);
	
	for(int u = 1 ; u <= n ; ++u)   {
		for(int i = 0 ; i < k ; ++i)    {
			if (d[i << 1][u] + d[i << 1 | 1][u] != d[i << 1][b[i]])
				continue;
			if (d[i << 1][u] == d[0][u] || (mask >> i & 1))
				num[u] |= (1 << i);
		}
	}
	
	function<void(int)> dfs = [&](int u)    {
		int &x = f[u];
		if (x >= 0) return;
		x = 0;
		for(ii  e : g[u])   {
			int v = e.X;
			int C = e.Y;
			if (d[0][u] + C == d[0][v] && d[1][u] == d[1][v] + C)   {
				dfs(v);
				if (num[u] > 1 && num[v] > 1)
					x = max(x,f[v] + C);	
			}
		}
	};
	
	memset(f,-1,sizeof f);
	
	dfs(a[0]);  cout << d[0][b[0]] - f[a[0]]<< endl;
}
/*
7 8 4
2 1 2
2 4 2
4 3 2
4 5 1
1 5 3
1 7 3
5 6 2
7 6 8
1 4
0 3 2
1 7 6
0 1 2
*/

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