Submission #1149758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149758		murpyl	Robot (JOI21_ho_t4)	C++20	0 / 100	3095 ms	20272 KiB

Main

#include <bits/stdc++.h>
using namespace std;
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 INF = 1e9;
int n,m;
struct Edge{
    int to, color, price, id;
};
vector<Edge> adj[maxn];
vector<pi> adj2[maxn];

int main(){
    setIO();
    cin>>n>>m;
    vector<pair<pi, pi>> edges(m);
    for (int i = 0; i < m; i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a--; b--;
        adj[a].pb({b, c, d, i});
        adj[b].pb({a, c, d, i});
        edges[i] = {{a,b}, {c,d}};
    }
    
    vi dist(n, INF);
    dist[0] = 0;
    priority_queue<pair<pi, pi>, vector<pair<pi, pi>>, greater<pair<pi, pi>>> pq;
    pq.push({{0,0}, {-1,-1}});
    while (!pq.empty()){
        auto [cur, prev] = pq.top();
        pq.pop();
        auto [d, node] = cur;
        auto [prevColor, prevId] = prev;
        if (d > dist[node]) continue;
        vi colors(m);
        vi sum(m);
        for (auto i : adj[node]){
            if (i.id == prevId && prevColor == -1){
                continue;
            }
            sum[i.color]+= i.price;
            colors[i.color]++;
        }
        for (auto to : adj[node]){
            int price = 0;
            int color = to.color;
            if (colors[to.color] > 1){
                int changeAll = sum[to.color] - to.price;
                if (changeAll > to.price){
                    color = -1;
                }
                price = min(changeAll, to.price);
            }
            if (dist[to.to] > d + price){
                dist[to.to] = d + price;
                pq.push({{dist[to.to], to.to}, {to.color, to.id}});
            }
            
        }
        
    }


    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:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 freopen((name+".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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+".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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