Submission #490133

#	Time	Username	Problem	Language	Result	Execution time	Memory
490133		rainliofficial	Robot (JOI21_ho_t4)	Java	Compilation error	0 ms	0 KiB

Main

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


struct Edge{
	int to, c, p, id;
};
struct State{
	int node, prevEdge, colorLater;
	ll cost;
};
bool cmp(const State& a, const State& b){
	return a.cost > b.cost;
}

const int MAXN = 2e5+5, MAXM = 4e5+5;
int n, m;
map<int, vector<Edge>> arr[MAXN];
map<int, ll> recolor[MAXN];
ll dp[MAXN];
int edge_color[MAXN], edge_cost[MAXN];
map<int, ll> dp2[MAXN];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);
	cin >> n >> m;
	for (int i=0; i<m; i++){
		int s, e, c, p;
		cin >> s >> e >> c >> p;
		s--; e--;
		recolor[s][c] += p;
		recolor[e][c] += p;
		arr[s][c].push_back({e, c, p, i});
		arr[e][c].push_back({s, c, p, i});
		edge_color[i] = c;
		edge_cost[i] = p;
	}
	for (int i=0; i<n; i++){
		dp[i] = 1e18;
	}
	priority_queue<State, vector<State>, decltype(&cmp)> pq(cmp);
	pq.push({0, -1, 0, 0});
	dp[0] = 0;
	while (!pq.empty()){
		State curr = pq.top();
		pq.pop();
		// cout << curr.cost << "\n";
		if (curr.colorLater == 1){
			if (dp2[curr.node][edge_color[curr.prevEdge]] != curr.cost){
				continue;
			}
			for (Edge e : arr[curr.node][edge_color[curr.prevEdge]]){
				if (e.id == curr.prevEdge){
                        continue;
                }
                ll nc = curr.cost + recolor[curr.node][e.c] - e.p;
                if (nc < dp[e.to]){
                    pq.push({e.to, e.id, 0, nc});
                    dp[e.to] = nc;
                }
			}
		}else{
			for (auto& s : arr[curr.node]){
				for (Edge e : s.second){
					if (e.id == curr.prevEdge){
						continue;
					}
					// Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
                    ll case1 = curr.cost + e.p;
                    if (case1 < dp[e.to]){
                        dp[e.to] = case1;
                        pq.push({e.to, e.id, 0, case1});
                    }   
                    // Recolor all other edges
                    ll case2 = curr.cost + recolor[curr.node][e.c] - e.p;
                    if (case2 < dp[e.to]){
                        dp[e.to] = case2;
                        pq.push({e.to, e.id, 0, case2});
                    }
                    // Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
                    // to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
                    ll case3 = curr.cost;
                    if (!dp2[e.to].count(e.c) || case3 < dp2[e.to][e.c]){
                        dp2[e.to][e.c] = case3;
                        pq.push({e.to, e.id, 1, case3});
                    }
				}
			}
			
		}
	}
	ll ans = dp[n-1];
	if (ans == 1e18) ans = -1;
	cout << ans << "\n";
}

Compilation message (stderr)

Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:3: error: class, interface, or enum expected
typedef long long ll;
^
Main.java:6: error: class, interface, or enum expected
struct Edge{
^
Main.java:8: error: class, interface, or enum expected
};
^
Main.java:9: error: class, interface, or enum expected
struct State{
^
Main.java:11: error: class, interface, or enum expected
	ll cost;
	^
Main.java:12: error: class, interface, or enum expected
};
^
Main.java:13: error: class, interface, or enum expected
bool cmp(const State& a, const State& b){
^
Main.java:15: error: class, interface, or enum expected
}
^
Main.java:18: error: class, interface, or enum expected
int n, m;
^
Main.java:19: error: class, interface, or enum expected
map<int, vector<Edge>> arr[MAXN];
^
Main.java:20: error: class, interface, or enum expected
map<int, ll> recolor[MAXN];
^
Main.java:21: error: class, interface, or enum expected
ll dp[MAXN];
^
Main.java:22: error: class, interface, or enum expected
int edge_color[MAXN], edge_cost[MAXN];
^
Main.java:23: error: class, interface, or enum expected
map<int, ll> dp2[MAXN];
^
Main.java:25: error: class, interface, or enum expected
int main(){
^
Main.java:29: error: class, interface, or enum expected
	cin >> n >> m;
	^
Main.java:30: error: class, interface, or enum expected
	for (int i=0; i<m; i++){
	^
Main.java:30: error: class, interface, or enum expected
	for (int i=0; i<m; i++){
	              ^
Main.java:30: error: class, interface, or enum expected
	for (int i=0; i<m; i++){
	                   ^
Main.java:32: error: class, interface, or enum expected
		cin >> s >> e >> c >> p;
		^
Main.java:33: error: class, interface, or enum expected
		s--; e--;
		^
Main.java:33: error: class, interface, or enum expected
		s--; e--;
		     ^
Main.java:34: error: class, interface, or enum expected
		recolor[s][c] += p;
		^
Main.java:35: error: class, interface, or enum expected
		recolor[e][c] += p;
		^
Main.java:36: error: class, interface, or enum expected
		arr[s][c].push_back({e, c, p, i});
		^
Main.java:37: error: class, interface, or enum expected
		arr[e][c].push_back({s, c, p, i});
		^
Main.java:38: error: class, interface, or enum expected
		edge_color[i] = c;
		^
Main.java:39: error: class, interface, or enum expected
		edge_cost[i] = p;
		^
Main.java:40: error: class, interface, or enum expected
	}
	^
Main.java:41: error: class, interface, or enum expected
	for (int i=0; i<n; i++){
	              ^
Main.java:41: error: class, interface, or enum expected
	for (int i=0; i<n; i++){
	                   ^
Main.java:43: error: class, interface, or enum expected
	}
	^
Main.java:45: error: class, interface, or enum expected
	pq.push({0, -1, 0, 0});
	^
Main.java:46: error: class, interface, or enum expected
	dp[0] = 0;
	^
Main.java:47: error: class, interface, or enum expected
	while (!pq.empty()){
	^
Main.java:49: error: class, interface, or enum expected
		pq.pop();
		^
Main.java:51: error: class, interface, or enum expected
		if (curr.colorLater == 1){
		^
Main.java:54: error: class, interface, or enum expected
			}
			^
Main.java:58: error: class, interface, or enum expected
                }
                ^
Main.java:60: error: class, interface, or enum expected
                if (nc < dp[e.to]){
                ^
Main.java:62: error: class, interface, or enum expected
                    dp[e.to] = nc;
                    ^
Main.java:63: error: class, interface, or enum expected
                }
                ^
Main.java:70: error: class, interface, or enum expected
					}
					^
Main.java:73: error: class, interface, or enum expected
                    if (case1 < dp[e.to]){
                    ^
Main.java:75: error: class, interface, or enum expected
                        pq.push({e.to, e.id, 0, case1});
                        ^
Main.java:76: error: class, interface, or enum expected
                    }   
                    ^
Main.java:79: error: class, interface, or enum expected
                    if (case2 < dp[e.to]){
                    ^
Main.java:81: error: class, interface, or enum expected
                        pq.push({e.to, e.id, 0, case2});
                        ^
Main.java:82: error: class, interface, or enum expected
                    }
                    ^
Main.java:86: error: class, interface, or enum expected
                    if (!dp2[e.to].count(e.c) || case3 < dp2[e.to][e.c]){
                    ^
Main.java:88: error: class, interface, or enum expected
                        pq.push({e.to, e.id, 1, case3});
                        ^
Main.java:89: error: class, interface, or enum expected
                    }
                    ^
Main.java:96: error: class, interface, or enum expected
	if (ans == 1e18) ans = -1;
	^
Main.java:97: error: class, interface, or enum expected
	cout << ans << "\n";
	^
Main.java:98: error: class, interface, or enum expected
}
^
57 errors