Submission #1149782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149782		murpyl	Robot (JOI21_ho_t4)	C++20	100 / 100	752 ms	82612 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}

const int maxn = 1e5+10;
const int maxm = 2e5+10;
const int INF = 1e18;
int n,m;
struct Edge{
    int to, color, price;
};
// vector<Edge> adj[maxn];
// int colorsum[maxn][maxm];
// int dist2[maxn][maxm];

map<int, vector<Edge>> adj[maxn];
map<int, int> colorsum[maxn];
map<int, int> dist2[maxn];

signed main(){
    setIO();
    cin>>n>>m;
    for (int i = 0; i < m; i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a--; b--;
        adj[a][c].pb({b, c, d});
        adj[b][c].pb({a, c, d});
        colorsum[a][c] += d;
        colorsum[b][c] += d;
    }
    
    vi dist(n, INF);    
    dist[0] = 0;
    priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
    pq.push({0, {0, 0}});
    while (!pq.empty()){
        auto [d, node] = pq.top();
        pq.pop();
        auto [cur, color] = node;
        if (color){
            if (dist2[cur][color] < d) continue;
            for (auto e : adj[cur][color]){
                int case1 = d+colorsum[cur][e.color]-e.price;
                if (case1 < dist[e.to]){
                    dist[e.to] = case1;
                    pq.push({case1, {e.to, 0}});
                }

            }
        }
        else{
            if (dist[cur] < d) continue; 
            for (auto i : adj[cur]){
                for (Edge e: i.second){
                    int case1 = d + colorsum[cur][e.color] - e.price;
                    //flip all others
                    if (case1 < dist[e.to]){
                        dist[e.to] = case1;
                        pq.push({case1, {e.to,0 }});
                    }
                    
                    int case2 = d + e.price;
                    //flip this one
                    if (case2 < dist[e.to]){
                        dist[e.to] = case2;
                        pq.push({case2, {e.to, 0}});
                    }
                    int case3 = d;
                    if (!dist2[e.to].count(e.color) || case3 < dist2[e.to][e.color]){
                        dist2[e.to][e.color] = case3;
                        pq.push({case3, {e.to, e.color}});
                    }

                }
            }
        }
    }

    if (dist[n-1] == INF){
        cout<<-1<<endl;
    } else {
        cout<<dist[n-1]<<endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen((name+".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen((name+".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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