Submission #1121128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121128		dosts	Robot (JOI21_ho_t4)	C++17	34 / 100	3081 ms	83144 KiB

Main

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
map<int,int> dp[N];
map<int,int> sm[N];

void solve() {
    int n,m;
    cin >> n >> m;
    vector<pii> edges[n+1];
    vi c(m+1),p(m+1);
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b >> c[i] >> p[i];
        edges[a].push_back({b,i});
        edges[b].push_back({a,i});
        sm[a][c[i]]+=p[i];
        sm[b][c[i]]+=p[i];
        dp[a][i] = dp[b][i] = inf;
    }
    for (int i=1;i<=n;i++) dp[i][0] = inf;
    dp[1][0] = 0;
    using state = pair<int,pii>;
    priority_queue<state,vector<state>,greater<state>> pq;
    pq.push({0,{1,0}});
    while (!pq.empty()) {
        int cost = pq.top().ff;
        auto [city,last] = pq.top().ss;
        pq.pop();
        if (dp[city][last] < cost) continue;
        for (auto& [go,id] : edges[city]) {
            int costy = sm[city][c[id]];
            if (last && c[id] == c[last]) costy-=p[last];
            if (cost+costy-p[id] < dp[go][0]) {
                dp[go][0] = cost+costy-p[id];
                pq.push(state{cost+costy-p[id],{go,0}});
            }
            if (cost+p[id] < dp[go][id]) {
                dp[go][id] = cost+p[id];
                pq.push(state{cost+p[id],{go,id}});
            }
        }
    }
    int ans = inf;
    for (auto it : dp[n]) ans = min(ans,it.ss);
    if (ans < inf) cout << ans << '\n';
    else cout << -1 << '\n';
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);/* 
    #else 
        freopen("shortcut.in","r",stdin);
        freopen("shortcut.out","w",stdout); */
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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