Submission #408757

#	Time	Username	Problem	Language	Result	Execution time	Memory
408757		Cantfindme	Robot (JOI21_ho_t4)	C++17	34 / 100	3057 ms	56704 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 <edge> 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({b,c,p});
		adjlist[b].push_back({a,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 i : adjlist[x]) {
				if (i.c != c) continue;
				
				int nd = d + sum[x][c] - i.p;
				if (dist[i.v] == -1 or dist[i.v] > nd) {
					pq.push(pii(nd,pi(i.v,0)));
					dist[i.v] = nd;
				}
			}
		} else {
			if (d != dist[x]) continue;
			
			for (auto i: adjlist[x]) {
				int nd = d + i.p;
			
				//Take a (1)
				//Straight to dist
				if (dist[i.v] == -1 or dist[i.v] > nd) {
					dist[i.v] = nd;
					pq.push(pii(nd,pi(i.v,0)));
				}
				
				//Do a suspension
				nd = d;
				if (dp[i.v].count(i.c) == 0 or dp[i.v][i.c] > nd) {
					dp[i.v][i.c] = nd;
					pq.push(pii(nd,pi(i.v,i.c)));
				}				
				
				//Take a (2)
				nd = d + sum[x][i.c] - i.p;
				if (dist[i.v] == -1 or dist[i.v] > nd) {
					dist[i.v] = nd;
					pq.push(pii(nd,pi(i.v,0)));
				}
			}		
		}
 	}
 	
 	cout << dist[n];
}

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