Submission #858328

#	Time	Username	Problem	Language	Result	Execution time	Memory
858328		phoenix0423	Robot (JOI21_ho_t4)	C++17	100 / 100	815 ms	77108 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int N = 1e9 + 7;
const ll INF = 1e18;
struct edge{
	int to, p, c;
	edge(){}
	edge(int _to, int _p, int _c) : to(_to), p(_p), c(_c){}
};
vector<edge> adj[maxn];
map<int, int> col[maxn];
map<int, ll> dist[maxn], ttl[maxn]; // dist[pos][0] = no change

int main(void){
	fastio;
	int n, m;
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a, b, c, p;
		cin>>a>>b>>c>>p;
		a--, b--;
		adj[a].pb(edge(b, p, c));
		adj[b].pb(edge(a, p, c));
		col[a][c] ++, col[b][c] ++;
		ttl[a][c] += p, ttl[b][c] += p;
	}
	for(int i = 0; i < n; i++){
		for(auto [c, cnt] : col[i]) dist[i][c] = INF;
		dist[i][0] = INF;
	}
	dist[0][0] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> q;
	q.push({0, 0});
	while(!q.empty()){
		auto [d, pos] = q.top(); q.pop();
		if(dist[pos][0] != d) continue;
		for(auto [x, p, c] : adj[pos]){
			dist[x][c] = min(dist[x][c], dist[pos][0]);
			if(dist[x][0] > dist[pos][0] + p) dist[x][0] = dist[pos][0] + p, q.push({dist[x][0], x});
			if(dist[x][0] > min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p) dist[x][0] = min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p, q.push({dist[x][0], x});
		}
	}
	cout<<(dist[n - 1][0] < INF ? dist[n - 1][0] : -1)<<"\n";
}

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