Submission #981177

#	Time	Username	Problem	Language	Result	Execution time	Memory
981177		penguin133	Robot (JOI21_ho_t4)	C++17	24 / 100	938 ms	127880 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
vector <pii> adj[200005];
map <int, int> mp[200005];
bool precmp[200005];
map <int, int> dist[200005];
map <int, vector <int> > bruh[200005];

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		mp[a][c]++; mp[b][c]++;
		adj[a].push_back({b, {c, d}});
		adj[b].push_back({a, {c, d}});
		bruh[a][c].push_back(b);
		bruh[b][c].push_back(a);
	}
	priority_queue <pii, vector <pii>, greater <pii> > pq;
	dist[1][0] = 0;
	pq.push({0, {1, 0}});
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se.fi, z = pq.top().se.se; pq.pop();
		if(dist[y][z] < x)continue;
		if(y == n){
			cout << x;
			return;
		}
		if(!precmp[y]){
			precmp[y] = 1;
			mp[y][z]--;
			for(auto i : adj[y]){
				int cst = 0;
				if(1){
					cst = i.se.se;
					if(dist[i.fi].find(i.se.fi) == dist[i.fi].end() || dist[i.fi][i.se.fi] > x + cst){
						dist[i.fi][i.se.fi] = x + cst;
						pq.push({x + cst, {i.fi, i.se.fi}});
					}
				}
				if(mp[y][i.se.fi] <= 1){
					if(dist[i.fi].find(0) == dist[i.fi].end() || dist[i.fi][0] > x){
						dist[i.fi][0] = x;
						//cout << y << ' ' << z << ' ' << x << ' ' << i.fi << ' ' << 0 << '\n';
						pq.push({x, {i.fi, 0}});
					}
				}
			}
			mp[y][z]++;
		}
		if(bruh[y][z].size() == 2){
			for(auto i : bruh[y][z]){
				if(dist[i].find(0) == dist[i].end() || dist[i][0] > x){
					//cout << x << ' ' << i << ' ' << 0 << '\n';
					dist[i][0] = x;
					pq.push({x, {i, 0}});
				}
			}
		}
	}
	int ans = 1e18;
	for(auto [i, j] : dist[n]){
		//cout << i << ' ' << j << '\n';
		ans = min(ans, j);
	}
	cout << (ans == 1e18 ? -1 : ans);
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

Main.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~

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