oj.uz

Submission #934978

# Submission time Handle Problem Language Result Execution time Memory
934978 2024-02-28T09:43:20 Z BF001 Robot (JOI21_ho_t4) C++17
0 / 100
 61 ms 24776 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define oo 1e18
#define N 100005
#define M 200005
#define fi first
#define se second

typedef pair<int, pair<int, pair<int, int>>> iii;

struct ii
{	
	int v, c, cst;
};



int n, d[3][N], m, cle[M], u[M], v[M], cl[M], cst[M];
vector<int> adj[N];
map<int, int> sum[N];

void ditra(){
	for (int i = 1; i <= n; i++){
		d[1][i] = d[0][i] = oo;
	}
	priority_queue<iii, vector<iii>, greater<iii>> q;
	d[1][1] = d[0][1] = 0;
	q.push({0, {1, {0, 0}}});
	while (!q.empty()){
		int du = q.top().fi;
		int uu = q.top().se.fi;
		int typ = q.top().se.se.se;
		int laste = q.top().se.se.fi;
		q.pop();
		if (du != d[typ][uu]) continue;
		//cout << typ << " " << uu << ' ' << d[typ][uu] << "\n";
		for (auto x : adj[uu]){
			int vv = v[x];
			if (vv == uu) vv = u[x];
			int clr = cl[x];
			int cost = cst[x];
			int mi = 0;
			if (clr == cl[laste]) mi = cst[laste] * (typ == 1);
			if (typ == 1 && clr != cl[laste]) continue;
			int d1 = du + sum[uu][clr] - cost - mi;
			//if (uu == 1 && vv == 2) cout << "check : "<< du << " " << sum[uu][clr] << " " << cost << " " << mi << "\n";
			if (d1 < d[0][vv]){
				d[0][vv] = d1;
				q.push({d[0][vv], {vv, {x, 0}}});
			}
			int d2 = du + cost;
			if (d2 < d[1][vv]){
				d[1][vv] = d2;
				q.push({d[1][vv], {vv, {x, 1}}});
			}

		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
    	//int u, v, c, cst;
    	cin >> u[i] >> v[i] >> cl[i] >> cst[i];
    	adj[u[i]].push_back(i);
    	adj[v[i]].push_back(i);
    	sum[u[i]][cl[i]] += cst[i];
    	sum[v[i]][cl[i]] += cst[i];
    }

    ditra();

    int res = min(d[0][n], d[1][n]);
    if (res == oo) cout << -1;
    else cout << res;

}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14948 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Incorrect 3 ms 15008 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 24776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 2 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14948 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Incorrect 3 ms 15008 KB Output isn't correct
9 Halted 0 ms 0 KB -