Submission #379077

#	Time	Username	Problem	Language	Result	Execution time	Memory
379077		Atill83	Robot (JOI21_ho_t4)	C++14	100 / 100	971 ms	110680 KiB

Main

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;
typedef pair<ll, pii> tp;
unordered_map<int, ll> mp[MAXN];
unordered_map<int, ll> dp2[MAXN];
ll dp[MAXN];
unordered_map<int, vector<pll>> adj[MAXN];
int c[MAXN], p[MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int a, b, C, P;
        cin>>a>>b>>C>>P;
        
        mp[a][C] += P;
        mp[b][C] += P;

        adj[a][C].push_back({b, P});
        adj[b][C].push_back({a, P});
    }

    memset(dp, 0x7f, sizeof(dp));
    priority_queue<tp, vector<tp>, greater<tp>> pq;

    pq.push({0, {1, 0}});
    dp[1] = 0;

    while(!pq.empty()){
        tp cur = pq.top();
        pq.pop();
        int col = cur.ss.ss, node = cur.ss.ff;
        ll dist = cur.ff;
        if(cur.ss.ss != 0){
            if(dp2[node][col] < dist)
                continue;
            dp2[node][col] = dist;
            for(pii u: adj[node][col]){
                ll sum = dist + mp[node][col] - u.ss;
                if(dp[u.ff] > sum){
                    dp[u.ff] = sum;
                    pq.push({sum, {u.ff, 0}});
                }
            }
        }else{
            if(dp[node] < dist)
                continue;
            for(auto &y: adj[node]){
                for(auto edg: y.ss){
                    ll d1 = dist + mp[node][y.ff] - edg.ss;
                    if(d1 < dp[edg.ff]){
                        dp[edg.ff] = d1;
                        pq.push({d1, {edg.ff, 0}});
                    }

                    ll d2 = dist + edg.ss;
                    if(d2 < dp[edg.ff]){
                        dp[edg.ff] = d2;
                        pq.push({d2, {edg.ff, 0}});
                    }

                    ll d3 = dist;

                    if(!dp2[edg.ff].count(y.ff) || dist < dp2[edg.ff][y.ff]){
                        dp2[edg.ff][y.ff] = dist;
                        pq.push({d3, {edg.ff, y.ff}});
                    }
                }
            }
        }
    }

    cout<<(dp[n] > INF ? -1 : dp[n])<<endl;


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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