Submission #934965

#	Time	Username	Problem	Language	Result	Execution time	Memory
934965		BF001	Robot (JOI21_ho_t4)	C++17	0 / 100	417 ms	46860 KiB

Main

#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);
			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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42