Submission #1057126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057126		SalihSahin	Robot (JOI21_ho_t4)	C++14	34 / 100	1608 ms	2097152 KiB

Main

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

const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int inf = 1e17;

int32_t main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin>>n>>m;
    vector<array<int, 3> > adj[n+1];
    vector<int> price[n+1];

    for(int i = 0; i < m; i++){
        int u, v, c, p;
        cin>>u>>v>>c>>p;
        array<int, 3> a1 = {v, c, p};
        array<int, 3> a2 = {u, c, p};
        adj[u].pb(a1);
        adj[v].pb(a2);
    }

    vector<int> sum(m+1), cnt(m+1);
    vector<int> seen;

    for(int i = 1; i <= n; i++){
        price[i].resize(adj[i].size());

        for(auto itr: adj[i]){
            seen.pb(itr[1]);
            sum[itr[1]] += itr[2];
            cnt[itr[1]]++;
        }
        int ind = 0;
        for(auto itr: adj[i]){
            if(cnt[itr[1]] == 1) price[i][ind] = 0;
            else price[i][ind] = sum[itr[1]] - itr[2];
            ind++;
        }

        for(auto itr: seen){
            sum[itr] = 0;
            cnt[itr] = 0;
        }
        seen.clear();
    }

    map<int, int> vis[n+1];
    priority_queue<array<int, 5> > pq;
    pq.push({0, 1, 0, 0, 0});
    int ans = inf;

    while(!pq.empty()){
        int cost = -pq.top()[0];
        int node = pq.top()[1];
        int pre = pq.top()[2];
        int prec = pq.top()[3];
        int prep = pq.top()[4];
        pq.pop();

        if(vis[node][pre]) continue;
        vis[node][pre] = 1;
        if(node == n){
            ans = cost;
            break;
        }

        if(pre == 0){ // nothing changed
            int ind = 0;
            for(auto itr: adj[node]){
                if(price[node][ind] > 0) pq.push({-(cost + itr[2]), itr[0], node, itr[1], itr[2]});
                if(itr[2] > price[node][ind]) pq.push({-(cost + price[node][ind]), itr[0], 0, 0, 0});
                ind++;
            }
        }
        else{ // pre node changed, (- p[pre] in the case you dont change edge[node][nxt])
            int ind = 0;
            for(auto itr: adj[node]){
                if(price[node][ind] > 0) pq.push({-(cost + itr[2]), itr[0], node, itr[1], itr[2]});
                if(itr[2] > price[node][ind] - (itr[1] == prec ? prep: 0) ) pq.push({-(cost + price[node][ind] - (itr[1] == prec ? prep: 0)), itr[0], 0, 0, 0});
                ind++;
            }
        }
    }

    if(ans == inf) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

/*
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1
*/

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