Submission #518618

#	Time	Username	Problem	Language	Result	Execution time	Memory
518618		KhoaHo	Robot (JOI21_ho_t4)	C++11	100 / 100	192 ms	20248 KiB

Main

    #include <bits/stdc++.h>
    #define fi first
    #define se second
    #define mp make_pair
    using namespace std;
    struct edge {
    	int v,c,cost;
    	edge(){}
    	edge(int _v, int _c, int _cost) {
    		v = _v;
    		c = _c;
    		cost = _cost;
    	}
    };
     
    const int N = 1e5 + 5;
    const int M = 2e5 + 5;
    const long long oo = 1e18;
     
    vector <edge> adj[N];
     
    long long dis[2 * N];
    long long sum[M];
    long long best[M];
     
    int n,m;
     
    template <typename T> 
    bool mini(T &a, T b) {
    	if (a > b) {
    		a = b;
    		return true;
    	}
    	return false;
    }
     
    int main() {
    	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++) {
    		int u,v,c,w;
    		cin >> u >> v >> c >> w;
    		edge a = edge(v, c, w);
    		edge b = edge(u, c, w);
    		adj[u].push_back(a);
    		adj[v].push_back(b);
    	}
    	for (int i = 1; i <= n; i++)
    		dis[i] = oo;
    	
    	for (int i = 1; i <= m; i++)
    		best[i] = oo;
     
    	dis[1] = 0;
    	priority_queue <pair <long long, int>> heap;
    	heap.push(mp(0, 1));
    	while (heap.size()) {
    		int u = heap.top().se;
    		long long cur = -heap.top().fi;
    		heap.pop();
    		if (cur != dis[u])
    			continue;
     
    		for (edge e : adj[u]) {
    			sum[e.c] += e.cost;
    			best[e.c] = min(best[e.c], dis[e.v]);
    		}
     
    		for (edge e : adj[u]) {
    			int v = e.v;
    			int c = e.c;
    			int w = e.cost;
    			long long tmp = min(0LL + w, sum[c] - w);
    			if (mini(dis[v], cur + tmp)) 
    				heap.push(mp(-dis[v], v));
     
    			if (mini(dis[v], best[c] + sum[c] - w))
    				heap.push(mp(-dis[v], v));
    		}
     
    		for (edge e : adj[u]) {
    			sum[e.c] = 0;
    			best[e.c] = oo;
    		}
    	}
    	if (dis[n] == oo)
    		dis[n] = -1;
    	cout << dis[n];
    	return 0;
    }

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