Submission #1169350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169350		sunboi	Robot (JOI21_ho_t4)	C++20	0 / 100	319 ms	40856 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    int n, m; cin >> n >> m;
    vector<vector<vector<int>>> bad(n + 1);
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++){
        int a;
        vector<int> info(3);
        
        //[0] = b
        //[1] = color
        //[2] = coste
        cin >> a;
        cin >> info[0] >> info[1] >> info[2];
        
        bad[a].push_back(info);
        swap(a, info[0]);
        bad[a].push_back(info);
    }
    
    for (int i = 1; i <= n; i++){
        map<int, int> val;
        
        for (vector<int> u : bad[i]){
            val[u[1]] += u[2];
        }
        
        int mn = 0;
        if (val.size() == m){
            for (int j = 1; j <= m; j++){
                mn = min(mn, val[j]);
            }
        }
        
        for (vector<int> u : bad[i]){
            int best = min(mn + u[2], val[u[1]] - u[2]);
            g[i].push_back({u[0], best});
        }
    }
    /*for (int i = 1; i <= n; i++){
        cout << "i::::::" << i << endl;
        for (auto u : g[i]){
            cout << u.first << ' ' << u.second << endl;
        }
        cout << endl;
    }*/
    
    vector<long long> dist(n + 1, 1e18);
 
	priority_queue<pair<int, int>> pq;
 
	dist[1] = 0;
	pq.push({0, 1});
 
	while (!pq.empty()) {
		const auto [cdist, node] = pq.top();
		pq.pop();
		
		if (dist[node] != -cdist) continue;

		for (auto x : g[node]){
		    if (x.second - cdist < dist[x.first]){
		        dist[x.first] = -(cdist - x.second);
		        pq.push({cdist - x.second, x.first});
		    }
		}
	}
	
	if (dist[n] != 1e18) cout << dist[n] << endl;
	else cout << -1 << endl;

}

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