Submission #408760

#	Time	Username	Problem	Language	Result	Execution time	Memory
408760		Cantfindme	Robot (JOI21_ho_t4)	C++17	34 / 100	3083 ms	52916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
 
const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7; 

typedef pair<int, pi> pii;

//struct edge {
	//int v, c, p;
//};

vector <pii> adjlist[maxn];
map <int, int> dp[maxn], sum[maxn];
int dist[maxn];

int n, e;

int32_t main() {
	FAST
	
	cin >> n >> e;
	for (int i =0;i<e;i++) {
		int a,b, c, p;
		cin >> a >> b >> c >> p;
		adjlist[a].push_back(pii(b,pi(c,p)));
		adjlist[b].push_back(pii(a,pi(c,p)));
		sum[a][c] += p;
		sum[b][c] += p;
	}

	//(1) Only change edge i to completely unique colour (guaranteed to exist)
	//(2) Change rest of edges with same colour as edge i

	memset(dist,-1,sizeof dist);

	priority_queue<pii, vector<pii>,greater<pii>> pq;
	pq.push(pii(0,pi(1,0)));
	dist[1] = 0;
	
	while (!pq.empty()) {
		auto [d, cur] = pq.top(); pq.pop();
		auto [x, c] = cur;
		
		if (c != 0) {
			//We must take a (2) here if not void
			if (d != dp[x][c]) continue;
			
			for (auto [v,xx] : adjlist[x]) {
				auto [cc, p] = xx;
				
				if (cc != c) continue;
				
				int nd = d + sum[x][c] - p;
				if (dist[v] == -1 or dist[v] > nd) {
					pq.push(pii(nd,pi(v,0)));
					dist[v] = nd;
				}
			}
		} else {
			if (d != dist[x]) continue;
			
			for (auto [v, xx]: adjlist[x]) {
				auto [cc, p] = xx;
				
				int nd = d + p;
			
				//Take a (1)
				//Straight to dist
				if (dist[v] == -1 or dist[v] > nd) {
					dist[v] = nd;
					pq.push(pii(nd,pi(v,0)));
				}
				
				//Do a suspension
				nd = d;
				if (dp[v].count(cc) == 0 or dp[v][cc] > nd) {
					dp[v][cc] = nd;
					pq.push(pii(nd,pi(v,cc)));
				}				
				
				//Take a (2)
				nd = d + sum[x][cc] - p;
				if (dist[v] == -1 or dist[v] > nd) {
					dist[v] = nd;
					pq.push(pii(nd,pi(v,0)));
				}
			}		
		}
 	}
 	
 	cout << dist[n];
}

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42