oj.uz

Submission #1084002

# Submission time Handle Problem Language Result Execution time Memory
1084002 2024-09-04T19:02:31 Z I_FloPPed21 Robot (JOI21_ho_t4) C++14
0 / 100
 171 ms 42812 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=1e5+1;
const int M=2e5+1;
int n,m;
unordered_map<int,long long>mp[N];
vector<pair<int,pair<int,long long>>>adj[N];
long long dp[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        dp[i]=1e18;
    for(int i=1; i<=m; i++)
    {
        long long a,b,color,c;
        cin>>a>>b>>color>>c;
        adj[a].push_back({b,{color,c}});
        adj[b].push_back({a,{color,c}});
        mp[a][color]+=c;
        mp[b][color]+=c;
    }
    dp[1]=0;
    priority_queue<pair<long long,int>> pq={};
    pq.push({0,1});
    while(!pq.empty())
    {
        long long cost=-pq.top().first;
        int nod=pq.top().second;
        pq.pop();
        for(auto u:adj[nod])
        {
            long long cost1=u.second.second;
            long long cost2=mp[nod][u.second.first]-cost1;
            cost1=min(cost1,cost2);

            if(dp[u.first]>cost1+cost)
            {
                dp[u.first]=cost1+cost;
                pq.push({-dp[u.first],u.first});
            }

        }
    }

    if(dp[n]==1e18)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<dp[n]<<'\n';

    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Incorrect 3 ms 9052 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19832 KB Output is correct
2 Correct 22 ms 14300 KB Output is correct
3 Correct 54 ms 23520 KB Output is correct
4 Correct 32 ms 16984 KB Output is correct
5 Incorrect 171 ms 42812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Incorrect 3 ms 9052 KB Output isn't correct
10 Halted 0 ms 0 KB -