Submission #1149746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149746		murpyl	Robot (JOI21_ho_t4)	C++20	0 / 100	3094 ms	13140 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}};
    }
    //you don't have to change all of them if you only want to take 1 path
    for (int i = 0; i < n; i++){
        vi idx[m];
        for (auto j : adj[i]){
            idx[j.color].pb(j.id); 
        }
        for (int j = 0; j < m; j++){
            if (idx[j].size() > 1){
                for (auto k : idx[j]){
                pair<pi, pi> edge = edges[k];
                int x = edge.first.first, y = edge.first.second;
                int weight = edge.second.second;
                if (y == i){
                    swap(x,y);
                }
                adj2[x].pb({y, weight});
                }
            }
        }
    }
    vi dist(n, INF);
    dist[0] = 0;
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    pq.push({0,0});
    while (pq.size()){
        auto [d, node] = pq.top();
        pq.pop();
        if (d > dist[node]){
            continue;
        }
        for (auto i : adj2[node]){
            if (dist[i.first] > dist[node] + i.second){
                dist[i.first] = dist[node] + i.second;
                pq.push({dist[i.first], i.first});
            }
        }
    }

    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