Submission #1022761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022761		DucNguyen2007	Robot (JOI21_ho_t4)	C++14	100 / 100	309 ms	56680 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,m;
ll d[maxN+1];
struct duongdi
{
    int u;
    ll w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
priority_queue<duongdi> pq;
struct col
{
    int u,c;
    ll p;
};
vector<col> adj[maxN+1];
ll color[maxN+1];
unordered_map<int,ll> mp[maxN+1];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,c;
        ll p;
        cin>>u>>v>>c>>p;
        adj[u].push_back({v,c,p});
        adj[v].push_back({u,c,p});
        mp[u][c]+=p;
        mp[v][c]+=p;
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=inf;
    }
    d[1]=0;
    pq.push({1,0});
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        pq.pop();
        int u=tmp.u;
        ll w=tmp.w;
        if(d[u]<w)
        {
            continue;
        }
        for(auto i:adj[u])
        {
            color[i.c]=inf;
        }
        for(auto i:adj[u])
        {
            int v=i.u;
            ll tmp=mp[u][i.c]-i.p;
            color[i.c]=min(color[i.c],d[v]);
            if(d[v]>d[u]+tmp)
            {
                d[v]=d[u]+tmp;
                pq.push({v,d[v]});
            }
            if(d[v]>d[u]+i.p)
            {
                d[v]=d[u]+i.p;
                pq.push({v,d[v]});
            }
        }
        for(auto i:adj[u])
        {
            int v=i.u;
            ll tmp=mp[u][i.c]-i.p;
            if(d[v]>color[i.c]+tmp)
            {
                d[v]=color[i.c]+tmp;
                //cout<<v<<" "<<u<<" "<<mn<<" "<<tmp<<" "<<d[v]<<'\n';
                pq.push({v,d[v]});
            }
        }
    }
    if(d[n]==inf)
    {
        cout<<-1;
    }
    else cout<<d[n];
}

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