Submission #1078950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078950		_rain_	Robot (JOI21_ho_t4)	C++14	100 / 100	371 ms	132820 KiB

Main

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

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
//    freopen((name+".out").c_str(),"w",stdout);
    return;
}

const int maxn = 7e5;
const int maxm = 2e5;
struct Node{
    int to , c , p;
    Node(int to , int c , int p) : to(to) , c(c) , p(p) {};
};
int n , m;
vector<Node> g[maxn+2];
vector<pair<int,ll>> graph[maxn+2];
#define fi first
#define se second
bool used[maxm+2] , vis[maxn+2];
int tot = 0;
ll sum[maxm+2] , d[maxn+2];
void add_edge(int u , int v , ll cost){
    graph[u].push_back({v , cost});
    return;
}
map<int,int> vert[maxn+2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n >> m;
    for (int i = 1 ; i <= m; ++i){
        int u , v , c , p; cin >> u >> v >> c >> p;
        g[u].push_back(Node(v,c,p));
        g[v].push_back(Node(u,c,p));
    }
    tot = n;
    for (int i = 1; i <= n; ++i){
        for (auto& x : g[i]){
            if (!used[x.c])
                vert[i][x.c] = ++tot;
            used[x.c] = true;
        }
        for (auto& x : g[i]) used[x.c] = false;
    }
    for (int u = 1; u <= n; ++u){
        for (auto& x : g[u]) sum[x.c] += x.p;
        for (auto& x : g[u]){
            int v = x.to , c = x.c , p = x.p;
            add_edge(u , v , min((ll)p , sum[c] - p));
            add_edge(u , vert[v][c] , 0);
            add_edge(vert[u][c] , v , sum[c] - p);
        }
        for (auto& x : g[u]) sum[x.c] = 0;
    }
    memset(d,0x3f,sizeof d);
    ll INF = d[0];
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
    q.push({0 , 1});
    while (q.size()){
        ll cost = q.top().first;
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        d[u] = cost; vis[u] = true;
        for (auto& v : graph[u]){
            if (!vis[v.first]){
                q.push({cost + v.second , v.first});
            }
        }
    }
    cout << (d[n] == INF ? -1 : d[n]);
}

Compilation message (stderr)

Main.cpp: In function 'void SETIO(std::string)':
Main.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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